Background

As is well known, for many years Huashen has crushed various OJ, OI, CF, TC ... of course including CH.

Problem 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