题目描述

有 $n$ 个不同的人和 $n$ 道不同的题。

第 $i$ 个人开心当且仅当他被分配到 $i$ 道题。

求让至少一个人开心的分配方案数。

输入格式

一个正整数：$n$。

输出格式

一个数字：你的答案$\bmod 10^9+7$。

样例 #1

样例输入 #1

1

样例输出 #1

1

样例 #2

样例输入 #2

2

样例输出 #2

3

样例 #3

样例输入 #3

314

样例输出 #3

192940893

提示

数据范围

本题捆绑测试。

• 对于 $22 pts$ 的数据，$2\leq n\leq 7$。
• 对于另外 $33 pts$ 的数据，$1\leq n\leq 20$。
• 对于所有的数据，$1\leq n\leq 350$。

样例#2解释

有以下 $3$ 种方案：

• 第一题給第一个人，第二题給第二个人。

• 第二题給第一个人，第一题給第二个人。

• 两题都给第二个人。