TopCoder

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

33.3% (5/15)

Description

殿壬是個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲,而現在要講的,是殿壬出生後六個月又一天的故事。

由於殿壬是天才兒童,他在學完成乘法以及除法的隔一天變便會了最大公因數以及最小公倍數。當然,普通的最大公因數以及最小公倍數並不能滿足殿壬學習的熱忱,而且兩個整數的運算對他來說也太簡單太無趣了,因此他馬上發明了三個整數的「最小公因數」以及「最大公倍數」。對於整數 $a, b, c$ ,殿壬定義他們的「最小公因數」 $\text{lcd(a, b, c)} = \text{lcm}(\text{gcd}(a, b), c)$ ,「最大公倍數」 $\text{gcm(a, b, c)} = \text{gcd}(\text{lcm}(a, b), c)$ ,其中 $\text{gcd}(a, b)$ 以及 $\text{lcm(a, b)}$ 分別代表 $a, b$ 的最大公因數以及最小公倍數。

計算給定三個整數的「最小公因數」以及「最大公倍數」對殿壬來說當然太沒挑戰性了,因此殿壬計算的是:
$$ \prod_{1 \leq a, b, c \leq N}\left(\text{gcm}(a, b, c) \times \text{lcd}(a, b, c)\right) $$

亦即任三個介於 $1$ 到 $N$ 的正整數的「最小公因數」以及「最大公倍數」的乘積的乘積。

當然天才兒童如殿壬也可能計算錯誤,因此請你幫殿壬驗算看看吧!

Input Format

第一行有一個正整數 $T$ ,代表總共有幾筆測試資料。
接著 $T$ 行每行有一個正整數 $N$ 。

  • $1 \leq T \leq 10$
  • $1 \leq N \leq 3 \times 10^ 6$

Output Format

對於每一筆測試資料,輸出所求。由於答案可能很大,請輸出答案除以 $10^ 9 + 7$ 的餘數。

Sample Input

2
2
123

Sample Output

256
584744679

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~39 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 262144 262144 1
1 2000 262144 262144 1
2 2000 262144 262144 1
3 2000 262144 262144 1
4 2000 262144 262144 1
5 2000 262144 262144 1
6 2000 262144 262144 1
7 2000 262144 262144 1
8 2000 262144 262144 1
9 2000 262144 262144 1
10 2000 262144 262144 1
11 2000 262144 262144 1
12 2000 262144 262144 1
13 2000 262144 262144 1
14 2000 262144 262144 1
15 2000 262144 262144 1
16 2000 262144 262144 1
17 2000 262144 262144 1
18 2000 262144 262144 1
19 2000 262144 262144 1
20 2000 262144 262144 1
21 2000 262144 262144 1
22 2000 262144 262144 1
23 2000 262144 262144 1
24 2000 262144 262144 1
25 2000 262144 262144 1
26 2000 262144 262144 1
27 2000 262144 262144 1
28 2000 262144 262144 1
29 2000 262144 262144 1
30 2000 262144 262144 1
31 2000 262144 262144 1
32 2000 262144 262144 1
33 2000 262144 262144 1
34 2000 262144 262144 1
35 2000 262144 262144 1
36 2000 262144 262144 1
37 2000 262144 262144 1
38 2000 262144 262144 1
39 2000 262144 262144 1