题目描述

有 $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。