Description

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 < i_2 < \dots < i_m < 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 Format

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 < 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 Format

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

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

76

5 3 1789 15150
555 718 726
72 555
1029 718
5807 726
1002 718
7240 555

390415327