说明

时间限制：1 Sec 内存限制：256 MB 输入文件：led.in 输出文件：led.out

F 很闲，总是想出一些有趣的事情。今天他又想到了一个游戏。

我们准备了 $N$ 个编号为 $1 \sim N$ 的绿色 LED 灯，想要找出所有可能的操作顺序，把所有灯从绿色全部变成红色。

操作规则如下：

- 每个 LED 灯配有一个开关。

- 每按一次开关，灯的颜色变化为：绿色 → 黄色 → 红色。

- 已经变红的灯不能再进行任何操作。

请你帮 F 计算出合法的操作顺序总数，答案对 $1000000007$ 取模。

输入格式

输入一行一个整数 $N$。

输出格式

输出合法操作顺序的数量，对 $10^9+7$ 取模。

样例

样例 1

2

6

样例说明：

$N=2$ 时共 $6$ 种合法操作顺序

1. $1$变黄 → $2$变黄 → $1$变红 → $2$变红

2. $1$变黄 → $2$变黄 → $2$变红 → $1$变红

3. $2$变黄 → $1$变黄 → $1$变红 → $2$变红

4. $2$变黄 → $1$变黄 → $2$变红 → $1$变红

5. $1$变黄 → $1$变红 → $2$变黄 → $2$变红

6. $2$变黄 → $2$变红 → $1$变黄 → $1$变红

数据范围

对于 16% 的数据，$N \le 10$。

对于 48% 的数据，$N \le 1000$。

对于 56% 的数据，$N \le 10000$。

对于 100% 的数据，$1 \le N \le 10^7$。