P6042 "ACOI2020" School Festival

 Autumn is the season of studying, the season of eating, and, even more, the season of the school festival. As time passes, the school festival is getting closer and closer. Finally, the day has come, but unexpectedly, Yuji, who once ran into Nagisa wearing women’s clothing on Okinawa Island, actually showed up. Nakamura Rio (Nakamura Rio) saw this and hurriedly had Nagisa put on women’s clothing. There was no choice: since Yuji was already here, Nagisa gathered his courage and took the first step. (Why are you adding a hint box on your own!)

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$.**

**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$.

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

#### 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