C.打牌(future)

题目描述

你有 $n$ 张牌，第 $i$ 张牌上可以写上一个 $[L_i,R_i]$ 之间的整数。

预先给定你一个数组 $f[i]$ 以及一个数 $m$。

如果你在每张牌上写了一个数，并且第 $i$ 张牌上写的数是在 $[L_i,R_i]$ 之间的整数，则这是一种合法的写数方案。

假设你有一种写数的方案，记 $sum$ 为你在所有牌上写的数的和，我们定义这种写数方案的收益为 $f[ sum \bmod m]$ ，即先将 $sum$ 对 $m$ 取模，假设结果为 $x$，则收益为 $f[x]$。

你需要求出所有可能的合法的写数方案的收益的和对 $998244353$ 取模后的结果。

所有牌都是不同的，也就是说 $(1,2)$ 和 $(2,1)$ 是两种方案。

$(1,2)$ 表示第一张牌写了 $1$，第二张牌写了 $2$。

$(2,1)$ 表示第一张牌写了 $2$，第二张牌写了 $1$。

输入格式

第一行两个自然数 $n,m$ 。

接下来 $n$ 行，每行两个自然数，其中的第 $i$ 行表示第 $i$ 张牌上写的数需要是 $[L_i,R_i]$ 之间的整数。

接下来一行 $m$ 个自然数，表示 $sum$ 在 $0\sim m-1$ 的时候的收益，即依次表示 $f[0],f[1],\cdots,f[m-1]$ 的值。

输出格式

一行一个自然数，表示答案。

样例

输入样例 $1$

2 4
1 2
2 3
1 2 3 4

输出样例 $1$

8

输入样例 $2$

8 8
0 4
1 2
4 4
0 2
0 4
1 2
1 2
0 0
911114373 34661155 444172312 267937695 161566598 148199050 647048787 833671921

输出样例 $2$

563601763

数据范围

对于 $10\%$ 的数据，$n=1$ 。

对于 $30\%$ 的数据，$n,R_i,m\leq 8$ 。

对于 $50\%$ 的数据，$n\leq 20,m\leq 1000$ 。

对于 $70\%$ 的数据，$n\leq 50,m\leq 10^4$ 。

对于 $100\%$ 的数据，$1\leq n\leq 100,0\leq L_i\leq R_i< m\leq 10^6,1\leq f_i\leq 998244352$ 。

时间限制 : 3000 ms

空间限制 : 512 MB