暂无测试数据。

我们称一个长度为 $m+1$ 的自然数序列序列 $a$ 为「Q $m$ 序列」，当且仅当以下每一个条件都被满足：

1. $a_1=a_{m+1}=0$；
2. $\forall i\in[1,m]\cap N$，有 $a_i<m$；
3. $\forall i\in[1,m]\cap N$，有 $2a_i\equiv a_{i+1}\pmod m$ 或者 $2a_i+1\equiv a_{i+1}\pmod m$；
4. $\forall i,j\in[1,m]\cap N$，$i\ne j$，有 $a_i\ne a_j$。

其中 $N$ 为自然数集

给出 $m$，你需要求出「Q $m$ 序列」的个数对 $10^9+7$ 取模的结果。

输入格式

输入一行一个正整数 $m$。

输出格式

输出一行一个非负整数，表示「Q $m$ 序列」的个数对 $10^9+7$ 取模的结果。

数据规模与约定

对于 $10\%$ 的数据，$m\le2$；

对于 $30\%$ 的数据，$m\le8$；

对于 $50\%$ 的数据，$m\le16$；

对于 $80\%$ 的数据，$m\le32$；

对于 $100\%$ 的数据，$1\le m\le512$。

3

0

4

1

50

629145