#P18207. Subsequence Counting

Subsequence Counting

Subsequence Counting

给定一个长度为 mm 的序列 tt,以及一个长度为 LL 的序列 ss。序列 ss 从左到右由 nn 个连续段组成:第 ii 段包含 lil_i 个相同的元素,它们的值均为 viv_i。

给定正整数 kk,保证 gcd⁡(k,L)=1\gcd(k,L)=1。将 ss 按照下述规则重新排列,得到序列 s′s':

s(i⋅k) mod L′=si,0≤i<L.s'_{(i\cdot k)\bmod L}=s_i,\qquad 0\le i<L.

这里 ss 和 s′s' 的下标均从 00 开始。

求 tt 作为 s′s' 的子序列出现的次数。也就是说,求满足下述条件的下标组 (i1,i2,…,im)(i_1,i_2,\ldots,i_m) 的数量:

$$0\le i_1<i_2<\cdots<i_m<L, \qquad s'_{i_j}=t_j\quad(1\le j\le m).$$

由于答案可能很大,输出其对 998244353998244353 取模后的结果。

输入格式

第一行包含四个整数 n,m,k,Ln,m,k,L。

第二行包含 mm 个整数 t1,t2,…,tmt_1,t_2,\ldots,t_m。

接下来 nn 行,第 ii 行包含两个整数 li,vil_i,v_i,描述原序列的第 ii 段。

输出格式

输出一个整数,表示答案对 998244353998244353 取模后的结果。

数据范围

  • 1≤n≤20001\le n\le 2000;
  • 1≤m≤101\le m\le 10;
  • 1≤k<L≤1091\le k<L\le 10^9,且 gcd⁡(k,L)=1\gcd(k,L)=1;
  • 1≤ti,vi≤10001\le t_i,v_i\le 1000;
  • 1≤li≤1091\le l_i\le 10^9,且 ∑i=1nli=L\sum_{i=1}^n l_i=L。

输入只有一组数据。相邻两个段的值可以相同。

样例一

输入:

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