Trong một phòng thí nghiệm robot, một con robot có ~n~ cánh tay được đánh số từ ~1~ tới ~n~. Mỗi cánh tay cần được thực hiện đủ hai bước theo thứ tự:

• Bước ~1~: gắn cảm biến (sensor).

• Bước ~2~: gắn bộ truyền động (actuator).

Một kỹ thuật viên sẽ thực hiện lần lượt các thao tác này. Tuy nhiên:

• Mỗi lần chỉ được gắn cảm biến cho một cánh tay chưa được gắn cảm biến bất kỳ.

• Mỗi lần chỉ được gắn bộ truyền động cho một cánh tay đã có cảm biến nhưng chưa có bộ truyền động.

Hai cách thực hiện được coi là khác nhau nếu thứ tự chọn cánh tay để gắn cảm biến hoặc bộ truyền động là khác nhau.

Yêu cầu: Hãy tính số cách để hoàn thành việc lắp đặt cho tất cả ~n~ cánh tay.

Input

• Dòng đầu tiên chứa một số nguyên dương ~T~ là số lượng test.

• Mỗi test gồm một dòng chứa số nguyên dương ~n~.

Output

In ra ~T~ dòng, mỗi dòng là số cách thực hiện tương ứng với mỗi test.

Do kết quả rất lớn, in ra kết quả theo modulo ~1000000007~.

Scoring

Sample Input 1

2
1
2

Sample Output 1

1
6

Notes

Với ~n = 2~, các cách thực hiện gồm:

1s 1a 2s 2a

1s 2s 1a 2a

1s 2s 2a 1a

~3~ cách còn lại tương tự khi bắt đầu từ cánh tay ~2~.

Trong đó:

• is: gắn cảm biến cho cánh tay ~i~.

• ia: gắn bộ truyền động cho cánh tay ~i~.