描述

设 sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N，现在要问你 $\prod_{i=1}^{N}\text{sum}(i)$ ，也就是 $\text{sum}(1)\sim\text{sum}(N)$ 的乘积。

格式

输入

一个正整数 N。

输出

一个数，答案模 10000007 的值。

示例

3

2

提示

对于 100% 的数据，$1 ≤ N ≤ 10^{15}$。 ($10^{15} = 1,000,000,000,000,000$)