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

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
2019-08-20 06:24:38
k cần số lớn one hit
2018-10-06 19:07:04
cout random AC :)
2017-10-09 14:36:44
10^15 * 10^5 sẽ bị tràn số, phải cài bignum, nhớ đấy ^^
{dinh truong lam}
2017-07-17 07:16:27
one hit ac mà không cần xử lý số lớn
bài này để time lỏng quá

Last edit: 2017-07-17 07:19:34
2015-11-23 03:25:52 bembembem
trau cung AC
2015-10-29 15:10:36
Hit: Tính tổng các lũy thừa matrix bằng chặt nhị phân.

Last edit: 2015-10-29 16:07:06
2015-06-22 07:25:26 Duc M. Pham
Bài này đúng là khoảng cách từ nghĩ ra thuật đến code AC là rất xa :v
2015-06-22 06:41:03 ??? Ares
@lucky++ đúng rồi bạn :D
2015-06-20 03:41:23 lucky++
Các bạn đã AC cho tôi hỏi: n = 10^9 thì out là: 637832887717582 ?
2015-05-03 05:50:36 Tạ Ðặng Vĩnh Phúc
Có test bị lỗi hả >>>
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.