H. Subsequence Counting
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a sequence $$$\{t\}$$$ of length $$$m$$$ and a sequence $$$\{s\}$$$ of length $$$L$$$, where $$$\{s\}$$$ is composed of $$$n$$$ consecutive segments from left to right. The $$$i$$$-th segment contains $$$l_i$$$ identical elements, each with a value of $$$v_i$$$.

The sequence $$$\{s'\}$$$ is formed by shuffling the sequence $$$\{s\}$$$ according to a certain rule. Specifically, the sequence $$$\{s'\}$$$ satisfies $$$s'_{i \cdot k \bmod L} = s_i$$$ (indices start from $$$0$$$). Here, $$$k$$$ is a given positive integer constant, and it is guaranteed that $$$\gcd(k, L) = 1$$$.

Find the number of times $$$\{t\}$$$ appears as a subsequence in $$$\{s'\}$$$. Formally, if there is a strictly increasing sequence of indices $$$0 \le i_1 \lt i_2 \lt \dots \lt i_m \lt L$$$ such that for each $$$j = 1, 2, \dots, m$$$, $$$t_j = s'_{i_j}$$$, then $$$\{t\}$$$ is considered a subsequence of $$$\{s'\}$$$ at these indices. You need to determine how many different index groups satisfy this condition. Since the answer may be large, output the result modulo $$$998244353$$$.

Input

The first line contains four integers $$$n, m, k, L$$$ ($$$1 \le n \le 2 \times 10^3$$$, $$$1 \le m \le 10$$$, $$$1 \le k \lt L \le 10^9$$$, $$$\gcd(k, L) = 1$$$).

The second line contains $$$m$$$ integers representing the sequence $$$\{t\}$$$ ($$$1 \le t_i \le 10^3$$$).

The next $$$n$$$ lines describe the sequence $$$\{s\}$$$, each containing two integers $$$l_i, v_i$$$ ($$$1 \le l_i \le 10^9$$$, $$$1 \le v_i \le 10^3$$$). It is guaranteed that $$$\sum_{i=1}^n l_i = L$$$.

Output

Output a single integer, representing the result modulo $$$998244353$$$.

Examples
Input
4 2 17 27
3 1
10 3
6 1
10 3
1 1
Output
76
Input
5 3 1789 15150
555 718 726
72 555
1029 718
5807 726
1002 718
7240 555
Output
390415327