4129. 追月庙会游

【题目背景】

漂泊者与长离在追月节的时候一起在购物，但情商约等于 $0$ 的漂泊者让长离掏钱。长离十分无奈，但由于是漂泊者提出的请求，所以也只好答应，但她有一点问题，找到了你帮她解答。善良的你自然愉快地答应了。

【题目描述】

长离一共有 $n$ 种硬币，面值分别为 $c_1,c_2,c_3......$

她与漂泊者一共逛了 $m$ 次街，你可以假定 $n$ 种硬币有无限个，然而长离在路上总会碰到残象偷袭或熟人借钱，所以每次总会有第 $c_q$ 种硬币被借光，即不能使用。而每次逛街需要支付的钱为 $s$ 元，长离想让你帮她求出一共有多少种付钱方案是她能刚好支付 $s$ 元。

【输入格式】

第一行两个正整数 $n,m$，代表有 $n$ 种硬币与逛了 $m$ 次街。

第二行有 $n$ 个正整数，分别代表 $n$ 种硬币的面值。

接下来有 $m$ 行，每一行有两个正整数 $q,s$，分别代表第 $c_q$ 种硬币不能用与需要支付 $s$ 元钱。

【输出格式】

对于每次询问，请输出一个正整数代表付钱方案个数，将答案对 $998244353$ 取模。

【样例1输入】

4 2
1 2 5 10
2 10
3 900

【样例1输出】

4
20566

【样例2】

样例下载

【数据规模与约定】

对于 $20 \%$ 的数据，满足 $n,s \le 5 \times 10^3,m = 1,c_i \le 10^3$ 。

对于另外 $50 \%$ 的数据，满足 $n,s \le 5 \times 10^3,m \le 50,c_i \le 10^3$ 。

对于 $100 \%$ 的数据，满足 $n,s \le 5 \times 10^3,m \le 10^4,c_i \le 10^3$ 。

【来源】

校际联合邀请赛第5场-入门组T3