给定一个长为 的序列 和长为 的序列 ，序列 由 段连续的部分从左往右依次拼接而成，第 段包含 个相同的元素，每个元素的值都为 。
序列 由序列 按一定规则打乱形成。具体而言，序列 满足 （下标从 开始）。其中 是一个给定的正整数常数，且保证 。
求 在 中以子序列形式出现的次数。形式化地说，如果一组严格递增的索引 ，满足对于每个 ，都有 ，那么称 为 在这一组索引下的子序列。你需要求出有多少种不同的索引组满足这一条件。由于答案可能很大，你需要将答案对 取模。
第一行四个整数 (, , , )。
第二行 个整数表示序列 ()。
接下来 行描述序列 ，每行两个整数 (, )。保证 。
一行一个整数，表示答案对 取模后的结果。
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
