题目描述

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

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

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

输入格式

一个正整数：$n$。

输出格式

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

1

1

2

3

314

192940893

提示

数据范围

本题捆绑测试。

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

样例#2解释

有以下 $3$ 种方案：

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

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

• 两题都给第二个人。

说明

题目译自 COCI2019-2020 CONTEST #5 T5 Zapina ，译者 90693。