TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

64.7% (22/34)

Submission's AC Ratio

30.4% (31/102)

Tags

Description

8e7 最近在玩一個神奇的手機遊戲: 指數閒置!這是一個數學增量遊戲,目標是通過指數級的增長快速的使金錢盡量的多。遊戲裡有一些「理論」,可以看成是較小的支線任務,讓這些理論的金錢變多就可以加快主遊戲金錢成長的速度。

8e7現在看到的理論名為「二進位遞迴」,規則如下。一開始有一個長度為$n+1$的整數陣列$a = a_0, a_1,..., a_n$,其中$a_0 = 1$,其他數字由8e7所事先購買的升級決定。接下來此陣列會開始進行「迭代」,第$x$次迭代的規則如下:

若$x$是奇數,將$a_1$的值加上$a_0$,
否則,若$\frac{x}{2}$是奇數,將$a_2$的值加上$a_1$,
否則,若$\frac{x}{4}$是奇數,將$a_3$的值加上$a_2$,
...以此類推,若$k$是最大的非負整數使得$2 ^ k $整除$x$,那讓$a_{k+1}$的值加上$a_k$。如果此時$k+1 > n$,那麼陣列不會改變。

8e7接下來會掛機,且他已經知道在掛機的時間總共會進行$t$次迭代,而他現在就想要知道序列$a$最後的長相。於是他詢問了程式高手(對,就是你!)幫助他的忙。

喔對了,實際上$a$的數字可能會非常大,因此他只希望知道$a$中每個數字除$10 ^ 9 + 7$的餘數。

Input Format

第一行有兩個整數$n, t$,代表陣列長度與迭代次數。
第二行有$n$個數字$a_1, a_2,..., a_n$,代表一開始的陣列。

對於所有測資,$1 \leq n \leq 60, 1 \leq t \leq 10 ^ {18}, 0 \leq a_i \leq 10 ^ 9$。

Output Format

輸出只有一行,為$n$個以空白分隔的整數,第$i$個整數為$t$次迭代之後$a_i$除以$10 ^ 9+7$的餘數。

Sample Input 1

3 5
1 0 2

Sample Output 1

4 2 4

Hints

Problem Source

Inspired by: Exponential Idle

Subtasks

No. Testdata Range Constraints Score
1 0~4 $t \leq 10^ 6$ 11
2 5~9 $n \leq 2$ 6
3 5~14 $n \leq 4$ 19
4 0~22 無其他限制 64

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 65536 1 4
1 1000 131072 65536 1 4
2 1000 131072 65536 1 4
3 1000 131072 65536 1 4
4 1000 131072 65536 1 4
5 1000 131072 65536 2 3 4
6 1000 131072 65536 2 3 4
7 1000 131072 65536 2 3 4
8 1000 131072 65536 2 3 4
9 1000 131072 65536 2 3 4
10 1000 131072 65536 3 4
11 1000 131072 65536 3 4
12 1000 131072 65536 3 4
13 1000 131072 65536 3 4
14 1000 131072 65536 3 4
15 1000 131072 65536 4
16 1000 131072 65536 4
17 1000 131072 65536 4
18 1000 131072 65536 4
19 1000 131072 65536 4
20 1000 131072 65536 4
21 1000 131072 65536 4
22 1000 131072 65536 4