Cho số tự nhiên n \((n \le 100000)\). Hãy in ra hàng thứ \(n\) của tam giác Pascal. Cho biết tam giác Pascal có hình dạng như sau :

Hàng 0: 1
Hàng 1: 1 1
Hàng 2: 1 2 1
Hàng 3: 1 3 3 1
Hàng 4: 1 4 6 4 1
...

Yêu cầu: Với mỗi số tìm được, hãy in ra số dư của nó khi chia \(10^9 + 7\).

Input

• Dòng đầu chứa \(T\) (\(T \le 100\)) là số test.
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(n\).

Output

• Gồm \(T\) dòng, mỗi dòng là đáp số tương ứng với mỗi trường hợp \(n\).

Example

3
1
2
3

1 1
1 2 1
1 3 3 1