Cho số tự nhiên n (n<=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⁹+7.

Dữ liệu 

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

Kết quả 

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