Vòng dây

Có \(n\) thiết bị được đặt trên một vòng tròn, đánh số từ \(1\) đến \(n\).
Ban đầu có đúng \(n\) sợi dây, mỗi sợi nối hai thiết bị kề nhau:
thiết bị \(1\) nối với \(2\), \(2\) nối với \(3\), …, \(n-1\) nối với \(n\), và \(n\) nối với \(1\).

Bạn được phép cắt bỏ một số sợi dây bất kỳ (có thể cắt \(0\) sợi, hoặc cắt nhiều sợi).
Sau khi cắt, yêu cầu mỗi thiết bị vẫn còn ít nhất một sợi dây nối với nó.

Với mỗi \(n\), hãy đếm số cách chọn tập sợi dây bị cắt sao cho thoả mãn yêu cầu trên.
In kết quả theo modulo \(10^9+7\).

Input

Dòng đầu chứa số nguyên \(T\) \((1\le T \le 5)\) là số bộ test.

\(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(n\) \((3\le n \le 50000)\).

Output

Gồm \(T\) dòng, dòng thứ \(i\) in ra số cách tương ứng với test thứ \(i\), theo modulo \(10^9+7\).

Scoring

• Có \(30\%\) số điểm ứng với \(n \le 20\).
• \(70\%\) số điểm còn lại không có ràng buộc gì thêm.

Sample Input 1

2
3
6

Sample Output 1

4
18