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$的餘數。