아름다운 멀티셋

양의 정수로 이루어진 멀티셋 $A = \{a_1, a_2, \ldots, a_k\}$의 원소 합이 $n$이고, $1$부터 $n$까지의 모든 정수를 원소들의 합으로 순서를 구분하지 않고 유일하게 나타낼 수 있으면 $A$를 $n$-아름답다고 부른다. 예를 들어 $\{1, 2, 4\}$는 $7$-아름답고, $\{1, 1, 3\}$은 $5$-아름답다. 정수 $n$이 주어질 때 다음 합을 구하라. [\left(\sum\limits_{A\text{ is }n\text{-beautiful}}|A| \right) \bmod p.]

각 $n$에 대한 답을 계산할 때 $p = 10^9 + 7$ 또는 $p = 10^9 + 9$를 직접 선택할 수 있다.

첫째 줄에 정수 $t$ ($1 \le t \le 5$)가 주어진다. 이는 입력 파일의 테스트 케이스 수이다.

다음 $t$개의 줄에 각각 정수 $n_i$ ($1 \le n_i \le 10^{16}$)가 주어지며, 이에 대한 답을 출력해야 한다. 한 파일에 주어지는 모든 $n_i$는 서로 다르다.

$t$개의 줄을 출력한다. $i$번째 줄에는 $n_i$에 대한 답을 출력한다. 각 답은 $p = 10^9 + 7$ 또는 $p = 10^9 + 9$ 중 하나로 정확해야 하며, $p$는 테스트 케이스마다 독립적으로 선택할 수 있다. 선택한 $p$는 출력하지 않고 답의 나머지만 출력한다.