addition

题目描述

以下所说的所有 $m$ 进制 $D$ 位的数，允许高位有前导 $0$。

小 $h$ 有 $n$ 个 $m$ 进制 $D$ 位的数 $A_1,A_2 \cdots A_n$。

在做加法前，大 $H$ 会对其进行变换：随机选择一个下标与值域都为 $[0,m-1]$ 的序列 $P$（$m^m$ 种情况），将每个数的每个位的值，从 $x$ 变成 $P_x$。变换后的数记为 $B_1,B_2 \cdots B_n$。

小 $h$ 有 $Q$ 次询问，每次给出 $X$，他想要知道，在随机变换后，有多少个有序对 $(i,j)$，$1 \le i,j \le n$ 满足 $B_i+B_j \le X$，对于所有变换情况求和。其中 $X$ 也是 $m$ 进制 $D$ 位的数。注：$(i,j)$ 和 $(j,i)$ 是不同有序对。

答案对 $10^9+7$ 取模。

输入格式

第一行三个数 $n,m,D$。

接下来 $n$ 行每行 $D$ 个数，表示 $A$，从高位到低位输入。

接下来一行一个数 $Q$。

之后 $Q$ 行，每行 $D$ 个数，表示 $X$，从高位到低位输入。

输出格式

对于每个询问，输出一行表示答案，对 $10^9+7$ 取模。

输入 #1

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

输出 #1

20182
9865
18835

说明/提示

对于所有数据：

$1 \le n \le 5 \times 10^4$，$1 \le m \le 10^3$。

$1 \le D \le 5$，$1 \le Q \le 10$。

因为出题人比较懒，子任务如下：

共有 16 个子任务（0-15），最后一个子任务 10 分，其余每个子任务 6 分。

对于子任务 0-7：$n=2 \times 10^3$，其余的 $n=5 \times 10^4$。

对于子任务 0-3,8-11：$m=16$，其余的 $m=1000$。

对于子任务 $i$：$D=(i \mod 4)+2$。