410703: GYM104081 D Devil May Cry
Description
在 YahAHa 很喜欢的游戏《Devil May Cry》系列中,有一个角色 Dante ,拥有非常多的武器和招式。举例来说,在《Devil May Cry 5》中,Dante 有六把近战武器,六把远程武器,四种战斗风格,三种战斗形态。
每种武器,风格和战斗形态,都将赋予 Dante 不同的技能,因此,Dante拥有极为丰富的技能(超过200!),利用这些丰富的技能,你可以打出各种各样的花式连招。
现在,YahAHa 想要设计一些Dante的连招,连招由若干个依次释放的技能组成,假如在某个连招中一共释放了 $$$n$$$ 个技能,则这个连招可以描述成一个下标从 $$$1$$$ 开始的长度为 $$$n$$$ 的数列 $$$a$$$ ,数列中的每个项都是一个正整数,代表一个技能。
一个合法的连招要满足如下条件:
- YahAHa 只想用 $$$m$$$ 个技能组成连招,因此对于任意的 $$$1\leq i\leq n$$$ 要满足 $$$1\leq a_i\leq m$$$ (不必每个技能都用上), $$$m$$$ 由输入给出。
- 同一个技能不能释放太多次,因为那样会导致评分降低,若用 $$$cnt_i$$$ 表示连招中技能 $$$i$$$ 出现的次数,则对于任意的 $$$1\leq i\leq m$$$ ,要满足 $$$cnt_i\leq lim_i$$$ ,其中 $$$lim_i$$$ 由输入给出。
- 有些技能有释放限制,例如:只能在空中释放,因此在连招的某些特定位置不能释放某个技能,具体而言,有若干形如 $$$ a_{p_i}\neq s_i $$$ 的限制,$$$p_i$$$ 和 $$$s_i$$$ 由输入给出。
现在 YahAHa 想知道,有多少长度为 $$$n$$$ 的合法连招?由于他还想去打游戏,所以他让你帮他解决这个问题。由于答案可能会很大,YahAHa 只想知道答案对 $$$998244353$$$ 取模的结果。
Input第一行包括两个整数 $$$n,m$$$( $$$1\leq n\leq 20,1\leq m\leq 100$$$ )
接下来一行,包括 $$$m$$$ 个整数,其中第 $$$i$$$ 个数表示 $$$lim_i$$$ ,表示第二条限制 ( $$$0\leq lim_i\leq n$$$ )。
接下来一行包括一个整数 $$$r$$$ ( $$$0\leq r\leq 1000$$$ )
接下来 $$$r$$$ 行,每行两个正整数 $$$p_i,s_i$$$ ,表示第三条限制,$$$1\leq p_i\leq n,1\leq s_i\leq m$$$ 。
Output仅一个整数,表示答案对 $$$998244353$$$ 取模的值
ExamplesInput1 1 1 0Output
1Input
2 3 2 2 1 2 2 1 2 2Output
2Input
3 4 1 3 2 2 3 3 3 3 4 1 1Output
21