Bằng cách xếp những lá bài lại với nhau, ta có thể tạo nên những kim tự tháp cho riêng mình.

Vậy có bao nhiêu hình tam giác tạo nên từ các "cạnh" của tháp.

Tháp với độ cao từ \(1\) đến \(5\)

Input

• Dòng đầu, chứa số nguyên dương \(T\) (\(T \le 10^6\)) - số lượng câu hỏi.
• \(T\) dòng sau, mỗi dòng chứa một số nguyên dương \(n\) (\(n \le 10^9\)).

Output

• Gồm \(T\) dòng, mỗi dòng chứa số lượng hình tam giác với \(n\) tương ứng (lấy số dư cho \(10^9 + 7\)).

Example

3
1
2
3

1
5
13