Problem Statement

对于有向图 $G=(V,E)$，定义路径 $\{u_1,u_2,\cdots,u_k\}(u_i\in V)$ 为满足 $\forall 1\le i\lt k,(u_i,u_{i+1})\in E$ 的节点序列。定义这样一条路径的长度为 $k$。

对于有向图 $G$，定义一条长度为 $L$ 的路径的权值为 $(L-1)^T$。

给出若干形如 $(u,v)$ 的询问，对于每组询问，求出：所有从 $u$ 到 $v$ 的，长度不超过 $k$ 的路径的权值和。

因为答案可能很大，所以你只要输出答案对 $M=998,244,353$ 取模的结果即可。

Input Format

第一行五个空格隔开的正整数：$n,k,q,T$，依次表示点数，路径长度限制，询问数，以及权值定义中的常数。

接下来 $n$ 行，每行 $n$ 个空格隔开的整数，其中第 $i$ 行的第 $j$ 个数 $A_{i,j}$ 表示 $i$ 号点到 $j$ 号点的道路数量。

接下来 $q$ 行，每行两个空格隔开的整数 $u,v$，表示个询问。

Output Format

输出 $q$ 行，每行一个整数，表示每天的询问的答案。

Sample Input

2 3 1 2
0 1
1 0
1 1

Sample Output

4

Sample Explanation

有两条可能的路径：

• $\{1,2,1\}$，权值为 $2^2=4$；
• $\{1\}$，权值为 $0^2=0$。

因此答案为 $4+0=4$。

Constraints

对于所有数据，有 $1\le n,T\le 50$，$0\le A_{i,j}\lt M$，$0\le k\le 10^9$，$1\le q\le n^2$。

• Subtask $1$（$20\%$）：$k\le 100$；
• Subtask $2$（$20\%$）：$T=1$；
• Subtask $3$（$25\%$）：$T\le 5$；
• Subtask $4$（$20\%$）：$T\le 10$；
• Subtask $5$（$15\%$）：无特殊限制。

时间限制：$3\texttt{s}$

空间限制：$512\texttt{MB}$