Description

One day, Huashen came to give another lecture. As usual, there was a super hard problem afterwards... We weaklings suffered again. The problem is as follows: Let $\text{sum}(i)$ denote the number of $1$ s in the binary representation of $i$. Given a positive integer $N$, Huashen asks you to compute $\prod_{i=1}^{N}\text{sum}(i)$, that is, the product of $\text{sum}(1)\sim\text{sum}(N)$.

Input Format

A positive integer $N$.

Output Format

One integer: the answer modulo $10000007$.

3

2

Hint

Constraints: For $100\%$ of the testdata, $1 \le N \le 10^{15}$.

Translated by ChatGPT 5