题目描述

给定一个长为 $m$ 的序列 $\{t\}$ 和长为 $L$ 的序列 $\{s\}$，序列 $\{s\}$ 由 $n$ 段连续的部分从左往右依次拼接而成，第 $i$ 段包含 $l_i$ 个相同的元素，每个元素的值都为 $v_i$。

序列 $\{s'\}$ 由序列 $\{s\}$ 按一定规则打乱形成。具体而言，序列 $\{s'\}$ 满足 $s'_{i \cdot k \bmod L} = s_i$（下标从 $0$ 开始）。其中 $k$ 是一个给定的正整数常数，且保证 $\gcd(k, L) = 1$。

求 $\{t\}$ 在 $\{s'\}$ 中以子序列形式出现的次数。形式化地说，如果一组严格递增的索引 $0 \le i_1 < i_2 < \dots < i_m < L$，满足对于每个 $j = 1, 2, \dots, m$，都有 $t_j = s'_{i_j}$，那么称 $\{t\}$ 为 $\{s'\}$ 在这一组索引下的子序列。你需要求出有多少种不同的索引组满足这一条件。由于答案可能很大，你需要将答案对 $998244353$ 取模。

输入格式

第一行四个整数 $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$)。

第二行 $m$ 个整数表示序列 $\{t\}$ ($1 \le t_i \le 10^3$)。

接下来 $n$ 行描述序列 $\{s\}$，每行两个整数 $l_i, v_i$ ($1 \le l_i \le 10^9$, $1 \le v_i \le 10^3$)。保证 $\sum_{i=1}^n l_i = L$。

输出格式

一行一个整数，表示答案对 $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