VOSTRIBO - Tribonacci

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

 

Nói đến dãy số Fibonacci, chắc chắn ai trong chúng ta ít nhiều cũng đã biết tới. Bờm vừa được thầy của mình dạy cho về dãy Fibonacci, anh ta rất thích thú với dãy số này nhưng lại cảm thấy công thức của dãy số này quá đơn giản, do đó Bờm nghĩ đến một dãy số phức tạp hơn có công thức gần giống với dãy Fibonacci, Bờm đặt tên cho dãy đó là Tribonacci.

Dãy Tribonacci là dãy số có công thức như sau:

  • T(i) = i ; với mọi số nguyên dương i <= 3
  • T(i) = T(i-1) + T(i-2) + T(i-3) ; với mọi số nguyên dương i > 3

Bờm khoe dãy số mới với Tèo, vốn là một người rất thông minh nhưng cũng rất gian xảo nên Tèo đố bờm có thể tính được tổng N phần tử đầu tiên của dãy Tribonacci này. Tức là Bờm cần tính giá trị:

  • F(N) = T(1) + T(2) + T(3) + ... + T(N-1) + T(N).

Do giá trị N rất lớn nên hãy giúp Bờm tính và trả lời kết quả cho câu đố của Tèo nhé. Do giá trị rất lớn nên Bờm chỉ cần trả lời phần dư của kết quả sau khi chia cho 1015 + 7 (mod 1015 + 7)

Input

  • Dòng đầu tiên chứa số T, là số lượng test.
  • T dòng tiếp theo, mỗi dòng chứa số nguyên dương N

Output

  • Gồm T dòng, mỗi dòng là kết quả tương ứng cho từng test. Do kết quả rất lớn nên chỉ cần trả về phần dư cho 1015 + 7

Giới hạn

  • T <= 100.
  • Trong 10% số test có N <= 10000.
  • Trong toàn test có N <= 109

Example

Input:
5
1
2
3
4
5
1
Output:
1
3
6
12
23

  • Người up: yenthanh132