Trồng cây

Một công viên mới rất đẹp vừa được xây dựng ở Hà Nội. Harry được giao nhiệm vụ trồng cây trong công viên.

Công viên có thể hình dung như một lưới gồm $N$ hàng và $N$ cột. Các hàng được đánh số từ $1$ đến $N$ từ trên xuống dưới, các cột được đánh số từ $1$ đến $N$ từ trái sang phải. Ký hiệu ô ở hàng $i$, cột $j$ là $(i,j)$.

Harry cần trồng đúng $N$ cây sao cho mỗi hàng và mỗi cột có đúng một cây.

Lối vào công viên ở ô $(1,1)$ và lối ra ở ô $(N,N)$, nên Harry không được trồng cây ở $2$ ô này. Hơn nữa, phải tồn tại một đường đi từ lối vào đến lối ra mà khách tham quan chỉ cần đi sang phải hoặc đi xuống. Hiển nhiên khách không thể đi qua ô có cây.

Một số ví dụ với $N=4$ (T là ô có cây, dấu chấm là ô trống):

. . . T      T . . .      . T . .      . . . T
. . T .      . . . T      T . . .      . T . .
. . T .      . . T .      . . . T      . . T .
T . . .      . . . .      . . T .      T . . .
  (1)          (2)          (3)          (4)

• Công viên (1) không hợp lệ vì cột $3$ có $2$ cây.
• Công viên (2) không hợp lệ vì ô $(1,1)$ có cây và chỉ có $3$ cây.
• Công viên (3) không hợp lệ vì không thể đi từ $(1,1)$ đến $(4,4)$ chỉ bằng các bước sang phải hoặc xuống.
• Công viên (4) hợp lệ.

Hãy giúp Harry đếm số công viên hợp lệ. Hai công viên được coi là khác nhau nếu có ít nhất một cây ở vị trí khác nhau trong hai công viên.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên $T$ ($T\le {10}^5$) là số bộ dữ liệu.
• $T$ dòng tiếp theo, mỗi dòng chứa một số nguyên $N$ ($1\le N\le {10}^7$).

Dữ liệu ra

In ra đúng $T$ dòng, mỗi dòng là số cách trồng cây thỏa mãn mọi điều kiện. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le T\le {10}^5$.
• $1\le N\le {10}^7$.

Ví dụ