Bocchinacci

Points: 3.5

Time limit: 2.0s

Memory limit: 586M

Author:

Problem type

$B o c c h i$ 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ọ, $B o c c h i$ 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à $T r i b o n a c c i$ .

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 $B o c c h i$ 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 \leq 3$

$T_{i} = T_{i - 1} + T_{i - 2} + T_{i - 3}$ với $i \geq 4$

Nhiệm vụ của $B o c c h i$ 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 $B o c c h i$ có thể phá giải bí ẩn của dãy số này, và vượt qua thách thức của $T r i b o n a c c i$ , 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 \leq t \leq 100)$ .

Mỗi test gồm một số nguyên dương $N$ $(1 \leq N \leq 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

Copy

Đầu ra

Copy

Comments

1

TICHPX commented on Oct. 15, 2024, 8:17 a.m.

Làm thêm bài nữa đếm số xâu nhị phân không chứa 3 số "111"

0

NguyenHaKien_CNTT4_K63 commented on Oct. 15, 2024, 8:51 a.m.

vâng ạ