1021 - 二进制中的1

f(i)表示数字i中二进制1的数量，求f(1)f(2)...*f(n)：

Input

输入一个正整数n，n不超过10^15。

Output

输出一个数字表示答案，对10000007取模。

Examples

Input

10

Output

96
Time Limit 1 second
Memory Limit 128 MB
Discuss Stats
上一题 下一题