No testdata at current.

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

巡有个超级长的序列 $S$。为了快速地告诉你，巡告诉你 $S$ 由 $n$ 段相同数字段拼接而成，其中第 $i$ 段是 $l_i$ 个 $v_i$。

假设 $S$ 长度为 $L$，即 $L=\sum_{i=1}^n l_i$。

小由搞了些恶作剧，具体的，小由把 $S$ 重新拼接成了 $S'$。但是由于宇宙射线的影响，你惊奇的发现存在一个 $k\in \N_+$ 且 $\gcd(k,L)=1$ 满足对任意 $i=0,1,\dots,L-1$ 满足 $S'_{ik\bmod L}=S_{i}$。

小巡对新的字符串 $S'$ 很感兴趣。小巡告诉你了一个长度为 $m$ 的数列 $T$。你需要告诉小巡 $S'$ 中有多少个子序列为 $T$。输出答案对 $998244353$ 取模的模数。

两个子序列不同，当且仅当某一个数在原序列中对应的位置不同。

输入格式

第一行四个正整数表示 $n,m,k,L$。

接下来一行 $m$ 个正整数表示 $T$。

接下来 $n$ 行，每行两个正整数表示 $l_i,v_i$。

输出格式

一行一个正整数表示答案。

样例 $1$

【样例输入】

2 2 1 5
1 2
2 1
3 2

【样例输出】

6

【样例解释】

$S'=[1,1,1,2,2]$。

样例 $2$

【样例输入】

2 2 2 5
1 2
2 1
3 2

【样例输出】

5

【样例解释】

$S'=[1,2,1,2,2]$。

样例 $3$

【样例输入】

4 2 17 27
3 1
10 3
6 1
10 3
1 1

【样例输出】

76

数据范围

对所有数据，$L=\sum_{i=1}^n l_i$，$1\leq n\leq 2000$，$1\leq m\leq 10$，$1\leq k<L\leq 10^9$，$\gcd(k,L)=1$。