Rabbit 喜欢研究数学。她经常看到如下形式的定理及其证明：

定理：以下命题等价：(i) ...... (ii) ...... (iii) ...... (iv) ...... 证明：我们将证明 (i) $\Rightarrow$ (ii)，(ii) $\Rightarrow$ (i)，(ii) $\Rightarrow$ (iii)，(iii) $\Rightarrow$ (iv) 以及 (iv) $\Rightarrow$ (ii)。......

更一般且更正式地说，该定理声称 $N$ 个命题 $P_1, \dots, P_N$ 是等价的。为了证明这一点，需要给出一些蕴含关系 $P_{a_1} \Rightarrow P_{b_1}, \dots, P_{a_k} \Rightarrow P_{b_k}$，使得对于任意 $x$ 和 $y$ ($1 \le x \le N, 1 \le y \le N$)，$P_x \Rightarrow P_y$ 均可由这些蕴含关系推导得出。

Rabbit 有时觉得证明过程没有冗余但很长，她想知道对于给定的 $N$，有多少种这样的证明方案。一个证明方案是一组蕴含关系 $\{P_{a_i} \Rightarrow P_{b_i} \mid 1 \le i \le k\}$，它们能够证明该定理。这里我们不区分证明的顺序。例如，$\{P_1 \Rightarrow P_2, P_2 \Rightarrow P_3, P_3 \Rightarrow P_1\}$ 和 $\{P_3 \Rightarrow P_1, P_2 \Rightarrow P_3, P_1 \Rightarrow P_2\}$ 被视为相同。

如果一个证明方案在去掉其中任意一个蕴含关系后，剩余的蕴含关系无法证明该定理，则称该证明方案是“好的”（good）。如果一个证明方案包含的蕴含关系数量大于或等于 $2N - 3$，则称该证明方案是“长的”（long）。编写一个程序，计算好的且长的证明方案的数量，结果对 $1\,000\,000\,007$ 取模。

输入格式

输入格式如下：

$N$

第一行包含一个整数 $N$ ($2 \le N \le 100$)。

输出格式

输出一个整数：好的且长的证明方案的数量，对 $1\,000\,000\,007$ 取模。

样例

样例输入 1

3

样例输出 1

5

样例输入 2

4

样例输出 2

52