有 $N$ 名年轻的程序员正在克拉皮纳和萨格勒布（Krapina Zagreb）的冬令营中准备第二阶段的竞赛。Malnar 先生是秩序、纪律和刻苦工作的极力倡导者，他让程序员们排成一排，并给他们每个人分配了若干个（可能是零个）任务。他总共分发了 $N$ 个不同的任务，并且他知道，如果排在第 $i$ 位的程序员恰好得到了 $i$ 个任务，那么他就会感到高兴。
Malnar 先生有多少种不同的分发任务的方式，使得至少有一名程序员感到高兴？如果存在一名程序员和一项任务，在一种分发方案中该程序员得到了该任务，而在另一种方案中没有得到，则认为这两种分发任务的方式是不同的。
输入格式
第一行包含一个整数 $N$ ($1 \le N \le 350$)，含义如题面所述。
输出格式
输出所求的分发方案数模 $10^9 + 7$ 的结果。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 22 | $1 \le N \le 7$ |
| 2 | 33 | $1 \le N \le 20$ |
| 3 | 55 | 无附加限制。 |
样例
输入 1
1
输出 1
1
输入 2
2
输出 2
3
输入 3
314
输出 3
192940893
说明
样例 2 解释
使得至少有一名程序员感到高兴的任务分发方式有：
- 将第一个任务分给第一个程序员，第二个任务分给第二个程序员。
- 将第二个任务分给第一个程序员，第一个任务分给第二个程序员。
- 将两个任务都分给第二个程序员。