Description

To take advantage of this rich-but-foolish young master and increase his spending as much as possible, Rio tried hard to hint at Nagisa. With no other choice, Nagisa thought for a while and raised a question:

Given an $n$, define:

$$\Gamma(0)=1,\Gamma(n)={n!}$$ $$A_i^j=\frac{\Gamma(i)}{\Gamma(j)}$$

Compute:

$$\sum_{i=1}^n \sum_{j=1}^i \sum_{k=1}^j \gcd(A_{i-j}^j \times \Gamma(j),A_{j-k}^k \times \Gamma(k))$$

Nagisa read out the words written on the conversation board Rio held up: If you cannot answer the question within the given time, you have to buy the entire menu once!

Although Yuji has a lot of money, he does not want to eat too much, because this problem has $T$ subproblems.

Since the answer may be very large, output the answer modulo $10086001$.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case:

There is only one line with one integer $n$.

Output Format

For each test case, output one integer per line: the answer modulo $10086001$.

5
1
2
3
4
5

1
4
10
20
36

Hint

Constraints

This problem uses bundled testdata.

• Subtask 1 (20 points): $T \leq 10^3$, $n \leq 10^2$.
• Subtask 2 (30 points): $T \leq 10^6$, $n \leq 5 \times 10^3$.
• Subtask 3 (50 points): $T \leq 10^6$, $n \leq 10^6$.

For $100\%$ of the testdata, $1 \leq T,n \leq 10^6$.

Translated by ChatGPT 5