该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

无额外样例。

前置知识

popcount(x) 用来统计十进制整数 x 的二进制表示中含有的 1 的个数。

例如：popcount(1)=1, popcount(2)=1, popcount(3)=2.

问题描述

给出一个正整数 $N$，求 $\prod_{i=1}^N popcount(i)$ 的值。

答案可能很大，你只需要输出答案 mod $(10^7+7)$ 的值。

输入

一个整数 N。

输出

一个整数，表示答案 mod $(10^7+7)$ 的值。

样例1输入

4

样例1输出

2

样例2输入

8

样例2输出

24

样例3输入

571

样例3输出

2560979

样例4输入

1000000000000000

样例4输出

1030503

数据范围

$1 ≤ N ≤ 10^{15}$