23646번 - Handsome multisets 스페셜 저지다국어

Call a multiset of positive integers $A = \{a_1, a_2, \ldots, a_k\}$ $n$-handsome if the sum of its elements is equal to $n$, and each integer from $1$ to $n$ can be uniquely represented as a sum of its elements up to their order. For example, $\{1, 2, 4\}$ is $7$-beautiful, $\{1, 1, 3\}$ is $5$-beautiful. Given an integer $n$, find the following sum: \[\left(\sum\limits_{A\text{ is }n\text{-beautiful}}|A| \right) \bmod p.\]

You can choose $p = 10^9 + 7$ or $p = 10^9 + 9$ by yourself for each $n$ you are computing the answer.

The first line contains an integer $t$ ($1 \le t \le 5$) -- the number of test cases in the input file.

Each of the next $t$ lines contain one integer $n_i$ ($1 \le n_i \le 10^{16}$), for which you need to output the answer. It is guaranteed that all $n_i$ in one file are different.

Output $t$ lines. The $i$-th of them should contain the answer for the number $n_i$. Each answer has to be correct either with $p = 10^9 + 7$ or $p = 10^9 + 9$, and $p$ can be chosen independently for each test case. Note that you should not output the chosen $p$, only the remainder of the answer.