TopCoder

Adrien Wu
AC×29New TIOJ ?

User's AC Ratio

57.5% (23/40)

Submission's AC Ratio

28.8% (32/111)

Tags

Description

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

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

x是奇數,將a1的值加上a0
否則,若x2是奇數,將a2的值加上a1
否則,若x4是奇數,將a3的值加上a2
...以此類推,若k是最大的非負整數使得2k整除x,那讓ak+1的值加上ak如果此時k+1>n,那麼陣列不會改變。

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

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

Input Format

第一行有兩個整數n,t,代表陣列長度與迭代次數。
第二行有n個數字a1,a2,...,an,代表一開始的陣列。

對於所有測資,1n60,1t1018,0ai109

Output Format

輸出只有一行,為n個以空白分隔的整數,第i個整數為t次迭代之後ai除以109+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 t106 11
2 5~9 n2 6
3 5~14 n4 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