Description

莉櫻为了利用这个人傻钱多的少爷，尽全力提高消费额，努力地暗示渚同学。没办法，于是渚同学想了一下，提出了一个问题：

给出一个 $n$，定义：

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

求

$$\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))$$

渚同学念着莉櫻举起的对话板上写的字：如果不能在规定时间回答出问题的话，就要把菜单全部买一遍哦！

尽管勇次钱多，但是他并不想吃得太多，因为这个问题有 $T$ 个小问题！

由于答案可能太大，请将答案对 $10086001$ 取模。

Input Format

本题有多组数据。

第一行一个整数 $T$，表示数据组数。

对于每组数据：

只有一行一个整数 $n$。

Output Format

对于每组数据，一行一个整数，表示问题的答案对 $10086001$ 取模后的值。

5
1
2
3
4
5

1
4
10
20
36

Hint

数据范围

本题采用捆绑测试。

• 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$。

对于 $100\%$ 的数据，$1 \leq T,n \leq 10^6$。