Hàm \(F(a)\) với a là một dãy số nguyên \(n \geq 1\) phần tử \(a_1\), \(a_2\), \(a_3\), ... \(a_n\) được định nghĩa thông qua đoạn code sau :

    F(a) = 0;
    Duyệt i từ 2 đến n
    {
       k = 0;
       Duyệt e từ 1 đến i-1
       {
           Nếu a[e] < a[i] thì
           {
               k = k + 1;
           }
       }
       F(a) = F(a) + k * a[i];
    }

cuom1999 thích những thứ nhỏ bé (ví dụ như Small), do đó cuom1999 muốn ami tính hàm F với tất cả các dãy số tự nhiên có độ dài bằng 2. Quá dễ, đáp án luôn là +∞. Còn ami thích những ghứ vĩ đại, do đó ami muốn các bạn tính tổng tất cả các hàm F(a) với a là một hoán vị n phần tử. Vì kết quả có thể lớn, các bạn cần in ra đáp số chia dư 1000000007.

Input

• Dòng đầu tiên chứa 1 số nguyên dương \(q\) là số câu hỏi.
• \(q\) tiếp theo, mỗi dòng dòng chứa 1 số nguyên dương \(n\).

Output

• In ra \(q\) dòng, mỗi dòng ứng với một câu hỏi.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(1 \leq n \leq 10\), \(q\) = 1.

• Subtask \(2\) (\(30\%\) số điểm): \(1 \leq n \leq 100\), \(q\) = 1.

• Subtask \(3\) (\(60\%\) số điểm): \(1 \leq n \leq 10^6\), \(1 \leq q \leq 10^6\).

Example

4
1
2
3
4

0
2
24
240