~Bocchi~ là một nhân vật kỳ bí, nổi tiếng với khả năng suy luận vô tận và sức mạnh giải quyết những bài toán đầy thử thách. Một ngày nọ, ~Bocchi~ nhận được một nhiệm vụ tối mật: tìm hiểu về một dãy số cổ đại được gọi là ~Tribonacci~.

Dãy số này ẩn chứa những bí mật vĩ đại của vũ trụ, và nhiệm vụ của ~Bocchi~ là phải khám phá tổng ~N~ phần tử đầu tiên của dãy số này. Nhưng không đơn giản như thế, dãy số ~T~ này không theo quy luật thông thường, mà đòi hỏi sự tính toán với những con số khổng lồ lên đến hàng tỷ!

Dãy số ~T~ được xây dựng như sau:

~T_i = i~ với ~i \le 3~

~T_i = T_{i-1} + T_{i-2} + T_{i-3}~ với ~i \ge 4~

Nhiệm vụ của ~Bocchi~ là tính tổng của ~N~ phần tử đầu tiên trong dãy này:

~S(N) = T_1 + T_2 + T_3 + ... + T_N~

Những lời thì thầm trong bóng tối nhắc đến những bài toán chưa ai giải nổi, những tiếng gào thét vang vọng trong màn đêm... Liệu ~Bocchi~ có thể phá giải bí ẩn của dãy số này, và vượt qua thách thức của ~Tribonacci~, nơi mọi sai lầm đều dẫn đến sự trả giá?

Đầu vào

Dòng đầu tiên là số lượng bộ test ~t~ ~(1 \le t \le 100)~.

Mỗi test gồm một số nguyên dương ~N~ ~(1 \le N \le 10^9)~.

Đầu ra

Với mỗi test, in ra đáp án trên một dòng. Vì kết quả có thể rất lớn nên chỉ in ra phần dư khi lấy kết quả chia cho ~10^{15}+7~.

Ví dụ

Đầu vào

5
1
2
3
4
5

Đầu ra

1
3
6
12
23