H. 能量分配 / Energy

时间限制： 4.0 秒 空间限制： 1024 MiB

题目描述

小 Q 是星际小学光速飞船课的老师，她准备向学校的星际能源商店购买 n 个 本质不同的能量石，其中每个能量石具有一单位能量，且每个能量石有一个 1 到 n 之间的 正整数编号，每个能量石的编号互不相同。她想要把它们分给 m 名学生，帮助学生们 练习如何驾驶光速飞船。 在分配时， 每个能量石会恰好被分给一名学生， 且允许学生没有分配到任何能量石。 定义 ci 表示第 i 名学生分配到的能量石总数，即满足 ∑m i=1 ci = n 且 ci ≥ 0。两个能量 石的分配方案本质不同当且仅当 存在一个学生在两个方案中分配到的能量石的编号集合不同。例如对于两个能量石与两名学生，能量石 1 分给学生 1，能量石 2 分给学生 2 与能量石 1 分给学生 2，能量石 2 分给学生 1 被视为两种本质不同的方案，由于学生 在方案一中分配到的能量石的编号集合为 {1} 而在方案二中分配到的能量石的编号集 合为 {2}，所以被视为本质不同的方案。 然而，每名学生都想要自己分配到的用于光速飞船的能量石比其他学生分到的多， 因此如果一个学生分配到的能量石比其他学生分到的能量石要更多，那么他会将拥有更 大的满意度。 初始时每名学生的满意度为 1，则在分配完 n 个能量石后第 i 名学生的满意度可以 按照如下方式计算:

• 依 次考虑每一个除了 i 自己以外的学生 j，若 ci > c j，则 i 的满意度将会变为原 来的 Ai,j 倍；若 ci = cj，则 i 的满意度将会变为原来的 Bi,j 倍；若 ci < c j，则 i 的满意度将不会发生变化。保证满足 1 < B i,j < A i,j ≤ 109。 对于第 i 名学生，令其在分配完 n 个能量石后的满意度为按照如上方式考虑完除 自己以外的 m - 1 名学生后最终的满意度。现在小 Q 定义一个能量石的分配方案的权 值为在分完 n 个能量石后 m 名学生满意度之积， 小Q 想知道所有本质不同的能量分配 方案的权值和对 317 取模的结果。然而小 Q 是光速飞船课老师，不是光速计算课老师， 所以她希望精通光速计算的您，迅速告诉她这个结果对 317 取模的结果。 此外， 由于小Q 事先没有测试星际小学光速飞船的具体性能， 当光速飞船的性能不 同时，能量需求会发生变化。所以她会询问 q 个可能购买的能量石总数 n，对于每一个 n，您需要告诉她所有若她购买了 n 个能量石，所有能量石的分配方案的权值和对 317 取模的结果。

输入格式

从标准输入读入数据。 第一行输入一个正整数 m(1 ≤ m ≤ 12)，表示学生总数。

接下来的 m 行输入 m × m 的矩阵 A，其中每行 m 个正整数，第 i 行第 j 列表示 Ai,j 的取值，其中当 i = j 时 Ai,j = 0，当 i ̸= j 时有 1 < A i,j ≤ 109。 接下来的 m 行输入 m × m 的矩阵 B，其中每行 m 个正整数，第 i 行第 j 列表示 Bi,j 的取值，其中当 i = j 时 Bi,j = 0，当 i ̸= j 时有 1 < B i,j < A i,j。 之后一行输入一个正整数 q(1 ≤ q ≤ 100)，表示 q 个询问。 接下来的 q 行每行一个正整数 n(1 ≤ n ≤ 10^18)，表示询问当能量石总数为 n 时原 问题的答案。

输出格式

输出到标准输出。 输出 q 行，每行一个 [0, 317) 之间的整数，表示能量石的分配方案权值和对 317 取 模的结果。

样例

样例 1 输入

3
0 7 5
5 0 7
4 6 0
0 4 4
3 0 4
3 2 0
4
1
2
10
1000000000000000000

样例 1 输出

37
303
46
148

样例 1 解释

对于 n = 1，共有 3 种本质不同的能量石的分配方案，即将唯一的能量石分配给学 生 1, 2 或 3，每种方案的权值分别为 280, 420, 288，所有分配方案的权值和为 988，对 取模的结果为 37。 对于 n = 2，共有 9 种本质不同的能量石的分配方案，对于每一组满足 1 ≤ i, j ≤ 3 的正整数对 (i, j)， 能量石1 分配给学生 i， 能量石2 分配给学生 j 对应一组方案， 各方 案的权值如下表，其中第 i 行第 j 列的数表示将能量石 1 分配给学生 i，能量石 2 分配 给学生 j 所对应的分配方案的权值：

280 420 504
420 420 160
504 160 288

各方案的权值和为 3156，对 317 取模的结果为 303。