题目描述

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

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

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

输入格式

一个正整数：$n$。

输出格式

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

1

1

2

3

314

192940893

提示

数据范围

• 对于所有的数据，$1\leq n\leq 350$。

样例#2解释

有以下 $3$ 种方案：

• 第一题給第一个人，第二题給第二个人。
• 第二题給第一个人，第一题給第二个人。
• 两题都给第二个人。