#6097. 花神的数论题

题目描述

定义 $\text{sum}(i)$ 表示 $i$ 的二进制表示中 $1$ 的个数。
给出一个正整数 $N$，求： [ \prod_{i=1}^{N} \text{sum}(i) ] 即 $\text{sum}(1) \sim \text{sum}(N)$ 的乘积。

答案对 $10000007$ 取模。

输入格式

一个正整数 $N$。

输出格式

一个整数，表示答案模 $10000007$ 的结果。

样例

输入

3

输出

2

解释

• $\text{sum}(1) = 1$
• $\text{sum}(2) = 1$
• $\text{sum}(3) = 2$
  乘积：$1 \times 1 \times 2 = 2$

数据范围与提示

$1 \le N \le 10^{15}$

由于 $N$ 很大，不能直接枚举 $1$ 到 $N$，需要利用数位 DP 或组合计数的方法。