Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VOSTRIBO - Tribonacci

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vostribo


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
5 1 2 3 4 5
1
Output: 1 3 6 12 23

Được gửi lên bởi:Hacker7
Ngày:2014-09-20
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED

hide comments
2015-05-03 05:50:36 Tạ Ðặng Vĩnh Phúc
Có test bị lỗi hả >>>
2015-03-29 14:55:49 Phat
sao n=2 mà kết quả là 3
2014-11-28 11:01:51 Lương Ðức Tuấn Ðạt
1 đấm AC =))
2014-11-07 10:12:33 blueBUBBLE
hình như ...
2014-11-07 09:29:50 blueBUBBLE
1485
2014-10-06 20:05:12 ??? Ares
nhân ma trận + xử lí số lớn vật vã :v
2014-10-02 15:05:24 Change The World
có ai biết cách làm đc 10^9 ko :((
chắc phải có công thức trực tiếp chứ
2014-10-02 05:23:17 Nguyen minh anh
TRí cho tao bộ text đi bạn
2014-10-02 05:23:12 Nguyen minh anh
TRí cho tao bộ text đi bạn
2014-09-30 15:21:10 Trương Quang Trí
ai co test cho cai thu di
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.