GCD Factorial Summation

In this problem, you are given an integer n and asked to compute the following summation modulo 10086001:

\[ S = \sum_{i=1}^{n} \sum_{j=1}^{i} \sum_{k=1}^{j} \gcd\Bigl(A_{i-j}^{j} \times \Gamma(j),\; A_{j-k}^{k} \times \Gamma(k)\Bigr) \]

where the functions \(\Gamma\) and \(A_i^j\) are defined as

[ \Gamma(0)=1,\quad \Gamma(n)=n! \quad\text{for } n\ge1, ]

[ A_i^j= \frac{\Gamma(i)}{\Gamma(j)}. ]

Observe that

[ A_{i-j}^j \times \Gamma(j)=\frac{\Gamma(i-j)}{\Gamma(j)}\times\Gamma(j)=\Gamma(i-j)=(i-j)!, ]

and similarly

[ A_{j-k}^k\times \Gamma(k)=(j-k)!. ]

Thus, the summation becomes

[ S = \sum_{i=1}^{n} \sum_{j=1}^{i} \sum_{k=1}^{j} \gcd\Bigl((i-j)!,(j-k)!\Bigr). ]

A classical number theory result tells us that for any nonnegative integers \(a\) and \(b\),

[ \gcd(a!,b!)=(\min(a,b))!. ]

By letting \(a=i-j\) and \(b=j-k\), and rearranging the order of summation (define \(s=a+b\)), you can show that the summation is equivalent to

[ S = \sum_{s=0}^{n-1} (n-s)\left( \sum_{x=0}^{s} (\min(x,s-x))! \right). ]

Your task is to compute this sum modulo 10086001. Note that the input consists of T test cases.

Input Format: The first line contains an integer T, the number of test cases. Each test case consists of one line containing an integer n.

Output Format: For each test case, output a single integer: the value of S modulo 10086001.

Note: Use LaTeX formatting for all formulas.

inputFormat

The input begins with a line containing a single integer T (the number of test cases). Each of the next T lines contains an integer n.

Example:

2
1
2

outputFormat

For each test case, output the computed summation value modulo 10086001 on a separate line.

Example:

1
4

sample

1
1

1