[COCI2019-2020#5] Zapina

题目描述

有 $n$ 个**不同的**人和 $n$ 道**不同的**题。 第 $i$ 个人开心当且仅当他被分配到 $i$ 道题。 求让至少一个人开心的分配方案数。

输入输出格式

输入格式


一个正整数：$n$。

输出格式


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

输入输出样例

输入样例 #1

1

输出样例 #1

1

输入样例 #2

2

输出样例 #2

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$ 种方案： - 第一题給第一个人，第二题給第二个人。 - 第二题給第一个人，第一题給第二个人。 - 两题都给第二个人。 ### 说明 **题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #5](https://hsin.hr/coci/archive/2019_2020/contest5_tasks.pdf) _T5 Zapina_** ，译者 [90693](/user/90693)。