"把一個人的溫暖 轉移到另一個的胸膛 讓上次犯的錯反省出夢想。"(陳奕迅‧愛情轉移)
遙遠的南NECH是一個富庶的國家，也是Doggyee情調教的起源地，然而將Doggyee情調教的教義發揮到極致的人並不在NECH，而是一個鄰近NECH的強國中的一位勇者。
他的名字無人知曉，然而眾人給他的稱號是「黑章」－－黑暗的樂章。黑章是一個很有情調的人，對他而言最重要的兩個女生是他熱戀中的女友和一直放不下的前女友，而他的情調值和對兩個女生的感情會互相影響，不僅如此，他也會把對前女友的感情轉移到現任女友身上。假設某天黑章的情調為m，而他對前女友和現任女友的感情分別是n1,n2，則隔天他對前女友的感情就會變成n1+2*m，對現任女友的感情會變成n2+2*n1+3*m，而他的情調會加上對兩個女生的感情變成m+n1+n2。
例如，一開始黑章的情調是1，他對兩個女生的感情都是0，則過了k天後，他的情調和感情狀況會變成這樣：
k=0 -> m=1; n1=0; n2=0
k=1 -> m=1; n1=2; n2=3
k=2 -> m=6; n1=4; n2=10
k=3 -> m=20; n1=16; n2=36
你已經知道現在目前黑章的情調和感情，現在想請問你：過了k天之後，黑章對他的前女友和現任女友的感情有多少呢？
因為黑章的感情太龐大了，所以請你輸出答案 MOD 1000000007的結果。
第一行會有三個數字m,n1,n2，代表黑章一開始的時候，他的情調、他對前女友的感情和他對現任女友的感情。
第二行有一個整數T，代表接下來的詢問筆數。
接下來的T行，每行都有一個整數k，代表問你過了k天之後黑章的感情狀況。
對於每次詢問，輸出過了k天之後黑章對前女友的感情和對現任女友的感情(mod 1000000007)，中間以空格隔開。
1 0 0 3 1 2 3
2 3 4 10 16 36
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
共有五個測資點，限制分別如下：
1: T=1; n1,n2≤10; k≤15;
2: T=1; n1,n2≤10; k≤1000;
3~5: T≤10^5; n1,n2≤100; k<2^31;