暂无测试数据。

题目描述

蒜头君定义一个长度为 $m+1$ 的自然数序列序列 $a$ 为「蒜头-$m$ 序列」，当且仅当以下每一个条件都被满足：

1. $a_1=a_{m+1}=0$；
2. $1\leq i,j\leq n$，有 $a_i<m$；
3. 对于所有的$ 1\leq i\leq m $，有 $2a_i\equiv a_{i+1}\pmod m$ 或者 $2a_i+1\equiv a_{i+1}\pmod m$；
4. 对于所有的$1\leq i,j\leq m$，$i\ne j$，有 $a_i\ne a_j$。

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

输入格式

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

输出格式

输出一行一个非负整数，表示「蒜头-$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