Toto thích học lập trình với thầy Tichpx. Hôm nay học về vòng lặp for, Toto được thầy Tichpx dạy viết một đoạn chương trình như sau:

#include<stdio.h>
int main()
{
    int i,j,n,s=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++) s+=i*j;
    printf("%d",s);
}

Toto rất thích thú với chương trình này, nhưng khi nhập vào n quá lớn thì sẽ có kết quả ra không còn chính xác nữa nên thầy Tichpx yêu cầu là để kết quả tính ra tránh trường hợp tràn số thì sẽ chỉ cần in ra kết quả là s chia lấy phần dư cho \(1000000007 (10^9+7)\)

Input

Dòng đầu gồm số bộ test \(t (1 \leq t \leq 100)\)

Các dòng tiếp theo gồm \(t\) dòng mỗi dòng chứa một số nguyên dương tương ứng với giá trị n \((1 \leq n \leq 10^9)\)

Output

Gồm có \(t\) số nguyên tương ứng với kết quả chương trình của từng trường hợp kiểm thử cách nhau bởi một ký tự trống

Ví dụ

Input

3
5
123456789
456

Output

225 692821092 856806346