题目描述

设有一个从 $1$ 到 $n$ 的排列 $P = [p_1, p_2, \dots, p_n]$，初始时为任意打乱的排列。

定义如下过程反复作用于 $P$，直至 $P$ 恢复为升序排列：

1. 若 $P = [1, 2, \dots, n]$，则结束操作。
2. 扫描当前排列，若存在一个连续子区间 $[i, i+1, \dots, j]$，满足对于区间内任意相邻元素都有 $p_{k+1} - p_k = 1$，则将该区间视为一块粘连体。在后续操作中，该粘连体视作一个整体，不能被拆开。
3. 将当前的所有粘连体（包括未粘连的单元素块和已经粘连的多元素块）打乱顺序，并将它们首尾连接成新的排列 $P$，回到步骤 1。

注：步骤 2 中可以存在多个不相交的粘连区间，且粘连不可逆，即一旦粘连，不会拆开。

定义该过程的操作步骤数为执行“步骤 3”的次数，记为 $X$。求 $E(n) = \mathbb{E}[X]$，即初始为任意排列时，该过程结束所需的期望步骤次数。由于答案可能为有理数，输出其模 $10^9 + 7$ 意义下的值：

其中模运算应使用有理数模意义下的乘法逆元，即若 $E(n) = \frac{a}{b}$，应输出 $a \cdot b^{-1} \bmod (10^9 + 7)$，其中 $b^{-1}$ 是 $b$ 在模 $10^9+7$ 下的乘法逆元。

输入格式

一行一个整数 $n$ ($1 \leq n \leq 2000$)，表示排列的大小。

输出格式

一行一个整数，表示 $E(n) \bmod (10^9 + 7)$。

样例输入

3

样例输出

333333338

样例说明

当 $n = 3$ 时，期望操作次数 $E(3) = \dfrac 73$。

数据范围