该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制1s，空间限制256mb。

题目描述

控制台上有N个按钮。 每个按钮都需要按下一次。 每次你可以同时推几个按钮。
假设有4个按钮。 您可以一次按下按钮1和按钮3，然后一次按下按钮2和按钮4。
它可以表示为字符串“13-24”。 其他方式可能是“1-2-4-3”，“23-14”或“1234”。 注意“23-41”与“23-14”相同。
给定数量N，你的任务是找到不同的有效推动方式的数量。

输入格式

一行一个整数n

输出格式

一行一个模1e9+7的答案

样例输入

3

样例输出

13

数据范围

1<=n<=3000