题目描述
有 $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$ 种方案:
第一题給第一个人,第二题給第二个人。
第二题給第一个人,第一题給第二个人。
两题都给第二个人。