C1580 [Contest #11]E-ffort

内存限制:256 MB 时间限制:3000 ms

题目描述

※ 简洁题意在分隔线下方

「向前。」她默念着。手臂在她与生俱来的能力下重构,随晶花的破碎化成更完美的肢体为她而战。

主战场的敌人有 $n$ 个,数据结构有 $m$ 种。单薄的数据在现实中放大为黑压压的敌军,以及周身缭绕着一往无前锋芒的友军。

「向前。」她奔跑起来。残缺的代码片段呼啸着擦过她的脸颊,有光错觉似地在其中闪动。

第 $i$ 种数据结构有 $a_i$ 个,极限是 $b_i$。这个数值是经测试给出的精确判定,表示一个数据结构对敌人造成的伤害上限。比起过于精细的数据,替罪羊树更在意为什么伸展树在同她一起回来时突兀地消失。她绝无可能脱逃,替罪羊树判定。

「向前。」土地化为炙热的影子,树木成为模糊的弧度。它们向后远去了。纷乱的呐喊与咏唱中,她似乎能感受到自己的心跳。

一个数据结构会造成总共 $x$ 击,以未知的分配方式分配在所有敌人中,根据战术部署每个敌人至少会承担一次攻击。而 $x$ 的值也是不大于该数据结构的极限 $b$ 的未知正整数。替罪羊树了解到的信息里有着过多的未知,毕竟她并非线段树,也不知道此时线段树接收到的噩梦般的反馈。

「就连精锐也束手无策?」线段树看着依然在奋战的数据结构,眉头紧锁,「这一代题目为什么计数类这么多?」

你对这个种族的困境毫无兴趣,只想知道最终的出击方案数取模998244353​的值,也就是说——




简洁题意

有 $m$ 种数据结构(可把数据结构想像成游戏中的种族),第 $i$ 种有 $a_i$ 个,當中每个可給敌人造成至少 $1$ 次,至多 $b_i$ 次伤害。有 $n$ 名敌人,每人承担至少一次伤害。求总情况数模 $998244353$。

数据结构两两不同 (同种的任两个也不同),敌人两两不同。

两种方案不同当且仅当某个数据结构造成的伤害不同,或某个敌人受到的伤害不同。

输入格式

第一行两个正整数 $n,m(n\times m \le 10^5)$ ,表示敌人数量和数据结构种数。

接下来的 $m$ 行,第 $i$ 行两个正整数 $a_i ,b_i$ ($1 \le a_i \le 10^5, 1 \le b_i < 998244353)$ 表示第 $i$ 种数据结构的数量和伤害上限。

输出

一行一个数,表示所求答案。

样例

样例输入 1

1 1 2 2

样例输出 1

4

样例输入 2

2 2 1 2 1 3

样例输出 2

15

提示