#P18207. Subsequence Counting
Subsequence Counting
Subsequence Counting
给定一个长度为 的序列 ,以及一个长度为 的序列 。序列 从左到右由 个连续段组成:第 段包含 个相同的元素,它们的值均为 。
给定正整数 ,保证 。将 按照下述规则重新排列,得到序列 :
这里 和 的下标均从 开始。
求 作为 的子序列出现的次数。也就是说,求满足下述条件的下标组 的数量:
$$0\le i_1<i_2<\cdots<i_m<L, \qquad s'_{i_j}=t_j\quad(1\le j\le m).$$由于答案可能很大,输出其对 取模后的结果。
输入格式
第一行包含四个整数 。
第二行包含 个整数 。
接下来 行,第 行包含两个整数 ,描述原序列的第 段。
输出格式
输出一个整数,表示答案对 取模后的结果。
数据范围
- ;
- ;
- ,且 ;
- ;
- ,且 。
输入只有一组数据。相邻两个段的值可以相同。
样例一
输入:
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