Nhân dịp khánh thành siêu thị VINCOMPLAZA tại Đông Hà, Việt Anh được bố mẹ dẫn đi chơi tại khu vui chơi có trong siêu thị. Bạn ấy rất thích thú với các trò chơi ở đây, đặc biệt là trò chơi mang tên "G_SCORES" với hệ thống tính điểm vô cùng thú vị.

G_SCORES là trò chơi mới được các nhà phát triển tạo ra ~N~ màn chơi, màn chơi thứ ~i~ có cấp độ là ~i~. Hệ thống điểm thưởng cho các cấp độ của trò chơi được thiết lập như sau:

• Cấp độ ~i~ có điểm thưởng là số nguyên dương ~s_i~ có giá trị từ ~1~ đến ~N~. Các cấp độ được sắp xếp theo độ khó tăng dần ~(s_1 \leq s_2 \leq \ldots \leq s_n)~;

• Để đảm bảo người chơi vượt qua nhiều cấp độ sẽ được xếp hạng cao hơn, các nhà phát triển thiết lập quy tắc: Với một số ~k~ ~(2 \leq k \leq N)~ bất kỳ, tổng số điểm của ~k~ màn chơi phải lớn hơn tổng số điểm của mọi lần mà có số màn chơi ít hơn ~k~.

Yêu cầu: Cho ~N~ màn chơi, hỏi có bao nhiêu cách thiết lập hợp lệ để các nhà phát triển thiết lập hệ thống điểm cho các cấp độ thỏa mãn những điều kiện nêu trên?

Input

Vào từ tệp văn bản SCORES.INP có cấu trúc sau:

• Dòng đầu tiên chứa một số nguyên ~T~ ~(1 \leq T \leq 5)~ là số lượng bộ tests;

• ~T~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên ~N (2 \leq N \leq 5000)~ là số màn chơi.

Output

Ghi ra vào tệp SCORES.OUT gồm có ~T~ dòng, dòng thứ ~i~ theo thứ tự ghi phần dư của số cách thiết lập hệ thống điểm hợp lệ khi chia ~10^9 + 7~

Scoring

Sample Input 1

3
2
3
4

Sample Output 1

3
7
16

Notes

Ở ví dụ trên với ~N = 3~ ta có ~7~ dãy ~s_i~ tương ứng như sau:

• ~1 \space 1 \space 1~

• ~1 \space 2 \space 2~

• ~1 \space 3 \space 3~

• ~2 \space 2 \space 2~

• ~2 \space 2 \space 3~

• ~2 \space 3 \space 3~

• ~3 \space 3 \space 3~