以整数 $n$ 为起点的简单 Collatz 序列（Simple Collatz Sequence，简称 SCS）定义如下：

$$S(k) = \begin{cases} k/2 & \text{若 } k \text{ 为偶数} \\ k+1 & \text{若 } k \text{ 为奇数} \end{cases}$$

该序列为 $n, S(n), S(S(n)), \dots$，直到数值首次达到 1 为止。

例如，以 11 为起点，我们有： $11 \to 12 \to 6 \to 3 \to 4 \to 2 \to 1$

该序列总是以 1 结尾。（趣闻：困难 Collatz 序列将奇数 $k$ 映射为 $3k+1$。目前尚不清楚该序列是否总是以 1 结尾。）

令 $A(n)$ 为以 $n$ 为起点的 SCS 的步数。例如，$A(11) = 6$。

令 $C(n)$ 为满足 $A(m) = n$ 的整数 $m$ 的个数。例如，满足 $A(n) = 6$ 的整数有： $10, 11, 13, 24, 28, 30, 31, 64$

因此 $C(6) = 8$。

注意，若 $n > 2^m$，则 $A(n) > m$，因为我们需要至少进行 $(m+1)$ 次除以 2 的操作。

编写一个程序来计算 $C(m)$。

输入格式

输入包含一行，为一个十进制整数 $m$ ($1 \le m \le 40000$)，即需要计算 $C(m)$ 的值。

输出格式

输出包含一行，为 $C(m) \pmod{1000007}$ 的值。

样例

样例输入 1

6

样例输出 1

8

样例输入 2

12345

样例输出 2

540591