题目描述

N只小猴在分N只桃，如果第i只小猴恰好分到i只桃，它就会开心。求让至少一只小猴开心的分配方案数。

输入格式

第一行包含一个正整数 $N$，意义如题目描述。

输出格式

包含一行，表示答案对 $10^9+7$ 取模后的值。

样例 1

input

1

output

1

样例 2

input

2

output

3

至少能使一只小猴高兴的题目分配方案如下：

• 第一个桃分配给第一只小猴，第二个桃分配给第二只小猴；
• 第一个桃分配给第二只小猴，第二个桃分配给第一只小猴；
• 两个桃都分配给第二只小猴。

样例 3

input

314

output

192940893

数据范围与提示

对于全部数据，$1\le N\le 350$。

详细子任务附加限制及分值如下表：