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}$
