Có 2N viên bi và một bảng hình chữ nhật kích thước 2N (2 hàng, N cột).Chúng ta lần lượt đặt từng viên bi vào bảng chữ nhật theo quy tắc sau:

● Đặt viên đầu tiên ở vị trí bất kỳ.

● Từ viên thứ 2 trở đi, phải đặt viên bi ở ô trống và kề với một ô đã có bi được đặt trong đó trước rồi.

Hai ô được gọi là kề nhau nếu chúng có chung đỉnh.Đếm số cách đặt hết 2 * N viên bi vào bảng

Input

• Dòng đầu tiên chứa số nguyên T là số test.
• T dòng sau mỗi dòng chứa một số nguyên N.(1 ≤ N ≤ 1000)

Có 50% số test có N ≤ 400

Output

• T dòng, mỗi dòng là số cách đặt bi. Do số cách lớn nên chỉ cần in số dư của kết quả với 1000000007.

Sample

Input #1

3
1
2
3

Output #1

2
24
480

Problem source: Free Contest 14