Pog 正在观看一场锦标赛。这场锦标赛共有 2k 名选手,初始时,一共存在 n 种不同的分数,对于每个
i,有bi 名得分为 ai 的选手。选手们各自拥有一个 1 到 2k 之间的编号,其中第 j 个得分为 ai 的选手编
号为 。
每一轮比赛,2k 名选手会两两配对进行比赛。在一场比赛中:
• 如果两名选手分数不同,则分数较少的选手获胜;
• 如果两名选手分数相同,则编号较小的选手获胜。
每场比赛结束后,获胜者分数增加 1,失败者分数减少 1。
由于 Pog 在玩赛马娘,没有认真观看比赛过程。只知道经过一轮后,场上出现了 m 种得分,对于每个
i,有 di 名得分是 ci 的选手。
他现在想知道,有多少种不同的初始配对方案,能够使得比赛经过一轮后得分出现上述的分布。请输出
方案总数对 998244353 取模的结果。如果两个方案中存在选手与不同对手配对,则认为这两个方案是不
同的。
输入格式
输入第一行包含三个整数 k, n, m (1 ≤ k ≤ 5 × 106 , 1 ≤ n ≤ 5 × 104 , 1 ≤ m ≤ 105 )。
接下来 n 行,第 i 行包含两个整数 ai , bi (|ai | ≤ 109 , bi ≤ 200)。
接下来 m 行,第 i 行包含两个整数 ci , di (|ci | ≤ 109
, di ≤ 400)。