Một hoán vị ~p_1,p_2,…,p_n~ của ~n~ số tự nhiên ~1,2,…,n~ được gọi là hoán vị dốc nếu tồn tại chỉ số ~i~ ~(1 < i < n)~ sao cho:

• ~p_j > p_{j+1}~ ~∀ i ≤ j ≤ n-1~.
• ~p_j > p_{j-1}~ ~∀ 2 ≤ j ≤ i~.

Bạn hãy đếm số lượng hoán vị dốc với ~n~ cho trước. Vì kết quả có thể rất lớn nên bạn chỉ cần đưa ra phần dư trong phép chia số lượng hoán vị dốc cho ~10^9+7~.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên ~t~ ~(1≤t≤100)~ – số bộ dữ liệu.
• ~t~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~n~ ~(1 ≤ n ≤ 10^9)~ miêu tả một bộ dữ liệu.

Kết quả:

• Ghi ra ~t~ dòng, mỗi dòng là đáp án tương ứng với từng bộ dữ liệu.

Ràng buộc

• Subtask 1 (20%): ~n≤10,t=1~.
• Subtask 2 (20%): ~n≤1000~.
• Subtask 3 (60%): Như ràng buộc gốc

Ví dụ:

Input

2
2
3 

Output

0
2