题目背景
「话说回来,你是谁?」
『竟然来这一手吗......』
『也是呢......』
『毕竟你夺走了几千、几万的能力,』
『他们对脑部造成的负担不是一般地大,』
『还能正常与人交谈已经很好了。』
「......」
『我啊,』
『是你的恋人。』
题目描述
为了让 おとさか ゆう 恢复记忆, ともり なお 找到了 PZY 。
PZY 经过研究,发现能力主要是根据体内的能力基因决定的,并把一共 m 个能力基因用 1 到 m 表示,并依次分成了 n 个集合,第 i 个集合包含了编号从 (j=1∑i−1aj)+1 到 j=1∑iaj 的 ai 个能力基因。
经过大量的实验, PZY 发现基因的排序可以简化为一个数列,并按照需求, 定义一个数列被称为基因样品,当且仅当这个数列只由 1 到 m 的数字组成,对于属于第 i 个集合里的数字,满足在该数列中非严格单调递增,且在数列中出现的次数不超过 bi 。
特别的,一个基因样本的研究价值就是构成这个基因样本的所有数字之和,注意重复的数字也要重复计算。
为了帮助 おとさか ゆう 恢复记忆, PZY 想知道所有的基因样品的研究价值之和是多少。
由于答案非常大,所以他只想知道对于答案除以 998244353 的余数。
输入格式
第一行输入一个正整数 n 。
第 2 到第 n+1 行,包括 2 个正整数 ai,bi ,意义如题面所示。
输出格式
输出所有的基因样品的研究价值除以 998244353 的余数。
提示
样例一的解释:
这两个集合为 {1,2} 和 {3}。
对于长度为 1 的基因样本有:1,2,3 。
总价值为 1+2+3=6 。
对于长度为 2 的基因样本有:11,12,13,22,23,31,32,33 。
总价值为 1+1+1+2+1+3+2+2+2+3+3+1+3+2+3+3=33 。
其中数列 21 不满足集合 1 中的数在数列中非严格单调递增。
对于长度为 3 的基因样本有:113,123,131,132,133,223,232,233,311,312,313,322,323,331,332 。
总价值为 99 。
其中数列 111,112,122,222,333 的出现次数超过限制。
对于长度为 4 的基因样本的总价值为 162 。
所以总价值为 6+33+99+162=300 。
设 k=i∑bi 。
对于其中 10% 的数据 1≤n≤3,1≤k≤10,1≤ai≤5 。
对于另外 20% 的数据 n=1,1≤k≤105,1≤ai≤106 。
对于另外 30% 的数据 n=2,2≤k≤105,1≤ai≤106 。
对于 100% 的数据 1≤n≤k≤105,1≤ai≤106 。