Trên thế gian này có rất nhiều thứ đẹp đẽ. Những cảnh đẹp ở Ý có đẹp đẽ không? Có (vì Ý là quê của anh tôi). Những cô gái anime có đẹp đẽ không? Chắc chắn có (vì waifu của tôi nằm trong đó). Loli có đẹp không? Có chứ! Nhưng bạn biết thứ gì cũng đẹp đẽ không kém không? Những hoán vị đẹp đẽ.

Loli muốn đếm số lượng hoán vị đẹp đẽ. Hoán vị là một dãy số chứa ~n~ số nguyên khác nhau, có giá trị từ ~1~ tới ~n~ và được sắp xếp với thứ tự bất kỳ (~[1,3,2,5,4]~ là hoán vị, nhưng ~[1,2,2]~ hay ~[1,4,3]~ thì không).

Vậy hoán vị đẹp đẽ thì khác gì hoán vị thường? Có chứ! Hoán vị ~p~ có độ dài ~n~ ~(p_1, p_2, ..., p_n)~ được coi là đẹp đẽ khi thỏa mãn tính chất sau:

~\gcd (1 \cdot p_1, \, 2 \cdot p_2, \, \dots, \, n \cdot p_n) > 1~

trong đó ~gcd~ là viết tắt của Ước chung lớn nhất.

Input

• Dòng đầu chứa một số nguyên ~t~ (~1 \le t \le 100~) là số lượng testcase.
• Mỗi testcase chứa một số nguyên ~n~ (~1 \le n \le 10^6~).

Output

• Với mỗi testcase in ra một số nguyên duy nhất là số hoán vị đẹp đẽ.
• Vì số hoán vị đẹp đẽ có thể rất lớn, hãy in ra phần dư của chúng với ~10^9+7~.

Subtask

• Subtask 1 (~15\%~ điểm): ~n \le 8~.
• Subtask 2 (~15\%~ điểm): ~n \le 20~.
• Subtask 3 (~20\%~ điểm): ~n \le 100~.
• Subtask 4 (~20\%~ điểm): ~n \le 10^3~.
• Subtask 5 (~30\%~ điểm): Không có ràng buộc gì thêm.

Sample Input

4
1
2
6
30

Sample Output

0
1
36
738721209

Giải thích

• Ở testcase đầu tiên, ta chỉ có một hoán vị là ~[1]~, hoán vị này không đẹp vì ~\gcd(1 \cdot 1) = 1~.
• Ở testcase thứ hai, ta chỉ có một hoán vị đẹp đẽ là ~[2, 1]~ vì ~\gcd(1 \cdot 2, 2 \cdot 1) = 2~.