Một hoán vị \(p_{1},p_{2},\ldots,p_{n}\) của \(n\) số tự nhiên \(1,\ 2,\ \ldots,\ 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}\ \forall\ i \leq j \leq n - 1.\)

+ \(p_{j} > p_{j - 1}\ \forall\ 2 \leq j \leq 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 \leq t \leq 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 \leq n \leq 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.

Ví dụ:

Subtasks:

+ Subtask 1 (20%): \(n \leq 10,\ \ t = 1.\)

+ Subtask 2 (20%): \(n \leq 1000.\)

+ Subtask 3 (60%): Như ràng buộc gốc.