#p4453. [COCI2019-2020#5] Zapina

[COCI2019-2020#5] Zapina

[COCI2019-2020#5] Zapina

题目描述

有 nn 个不同的人和 nn 道不同的题。

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

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

输入格式

一个正整数:nn。

输出格式

一个数字:你的答案 mod 109+7\bmod 10^9+7。

样例 #1

样例输入 #1


1

样例输出 #1


1

样例 #2

样例输入 #2


2

样例输出 #2


3

样例 #3

样例输入 #3


314

样例输出 #3


192940893

提示

数据范围

本题捆绑测试。

  • 对于 22pts22 pts 的数据,2≤n≤72\leq n\leq 7。

  • 对于另外 33pts33 pts 的数据,1≤n≤201\leq n\leq 20。

  • 对于所有的数据,1≤n≤3501\leq n\leq 350。

样例#2解释

有以下 33 种方案:

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

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

  • 两题都给第二个人。