Một bữa tiệc có rất nhiều bàn tròn và lớn. Có $n$ vị khách đã đến để dự tiệc, hỏi có bao nhiêu cách sắp xếp chỗ ngồi cho $n$ vị khách này. Hai cách xếp chỗ được coi là khác nhau nếu tồn tại hai người $x$, $y$ mà $x$ ngồi ngay cạnh bên phải của $y$ trong cách xếp này nhưng trong cách kia thì không.

Input

Dòng đầu chứa số tự nhiên $T$ là số lượng test case.

$T$ dòng tiếp theo, mỗi dòng chứa một số tự nhiên $n$.

Output

Ghi $T$ dòng là kết quả tương ứng cho $T$ test case, chỉ cần in ra phần dư khi chia cho $10^9 + 7$.

Scoring

• $T ≤ 10^6, n ≤ 10^6$

• Có $30\%$ số test với $n ≤ 10$

• Có $20\%$ số test với $10 < n ≤ 20$

• Có $20\%$ số test với $20 < n ≤ 1000$

2
1
3

1
6