Ở ngôi trường ILA (Informaticians of LA), nơi hội tụ của những con người đam mê máy tính. Có một chiếc thanh máy hết sức kì lạ. Thang máy chỉ có ba nút: ~1, 2, 5~. Khi bấm vào một trong ba nút đó, thang máy sẽ đi lên với số tầng tương ứng. Cụ thể: khi bấm vào nút ~1~, thang máy sẽ đi lên thêm ~1~ tầng. Tương tự khi bấm vào nút ~2~, thang máy sẽ đi lên thêm ~2~ tầng. Và bấm vào nút ~5~, thang máy sẽ đi lên thêm ~5~ tầng. Ví dụ khi học sinh đang ở tầng ~4~ và bấm nút ~2~, thì thang máy sẽ đưa học sinh đến tầng ~6~ (vì ~4+2=6~).

Vì trường bắt buộc học sinh phải đi thang bộ khi đi xuống nên thang máy sẽ không có nút đi xuống. Bạn hãy tính xem một học sinh đang ở tầng ~1~ sẽ có bao nhiêu cách bấm để lên tầng ~N~, với ~N~ là một số nguyên cho trước.

Dữ liệu vào

Dữ liệu vào bao gồm nhiều testcase. Dòng đầu tiên chứa một số nguyên ~T~ ~(1 ≤ T ≤ 10^5)~ là số lượng testcase. Mỗi testcase gồm một dòng ghi số nguyên ~N~ ~(1 ≤ N ≤ 10^6)~ là tầng cần đếm số cách bấm nút để lên tầng đó.

Dữ liệu ra

Với mỗi testcase, in ra số cách bấm nút để học sinh từ tầng ~1~ có thể lên được tầng ~N~. Đáp án được viết dưới dạng modulo ~10^9 + 7~.

Sample Input

3
1
2
5

Sample Output

1
1
5

Giải thích

Ở testcase thứ ~3~, học sinh có ~5~ cách để từ tầng ~1~ lên tầng ~5~:

1. ~1-1-1-1~
2. ~1-1-2~
3. ~1-2-1~
4. ~2-1-1~
5. ~2-2~