背景

XWQ将XY序列进行升级，升级成了XY矩阵
但很多时候还是需要XY序列形式
XWQ想更快计算，所以来找你帮忙
并答应让你做XY国的交通管理员
那可是XY国最肥的差事

描述

给出\(A\ast A\)的矩阵\(App\)
多次询问，每次给出一个\(1\ast A\)的向量\(Aoo\)和一个数\(Krr\)
XWQ要求你回答\(Aoo\ast (App^{Krr})\)
对\(10^9+7\)取模

输入

第一行一个正整数A
接下来A行，每行A个自然数
其中第i行第j个数为\(App_{ij}\)
接下来一行一个正整数M，为询问次数
接下来M行每行A+1个整数
其中第一个数为Krr，Krr之后第i个数为\(Aoo_i\)

输出

M行，每行A个数，为给XWQ的回答

样例

输入

2
1 1
0 1
2
4 1 0
5 1 1

输出

1 4
1 6

范围

10% A<=3 M<=3 Krr<=6 \(App_{ij}\),\(Aoo_i\)<=9
50% A<=40 M<=60 Krr<=\(10^6\)
60% A<=60 M<=10 Krr<=\(10^6\)
80% A<=70 M<=80 Krr<=\(10^6\)
100% A<=100 M<=100 Krr<=\(10^7\) \(App_{ij}\),\(Aoo_i\)<=\(10^5\)

限制

1s
64M