题目描述

译自 COCI 2019/2020 Contest #5 T5「Zapina」

现有 $N$ 位年轻的程序竞赛选手正在 Krapina Zagreb 的冬令营中准备第二赛季的比赛。Malnar 先生十分重视秩序，规则和努力，他让选手排成一行，并分配给他们一定数量（可能为 $0$）的题。他分配了 $N$ 道不同的题。并且他知道如果第 $i$ 名选手被分配到恰好 $i$ 道题，他就会开心。

Malnar 先生有多少种不同的题目分配方式能使至少一名选手开心？两种题目分配方式被认为是不同的当且仅当存在一位选手和一道题，在这种方案中这名选手被分配到这道题但是在另一种方案中没有被分配到这道题。

输入格式

第一行包含一个正整数 $N$，意义如题目描述。

输出格式

包含一行，表示答案对 $10^9+7$ 取模后的值。

样例 1

1

1

2

3

至少能使一位选手高兴的题目分配方案如下：

• 第一道题分配给第一位选手，第二道题分配给第二位选手；
• 第一道题分配给第二位选手，第二道题分配给第一位选手；
• 两道题都分配给第二位选手。

314

192940893

数据范围与提示

对于全部数据，$1\le N\le 350$。

详细子任务附加限制及分值如下表：