#556. 「Antileaf's Round」咱们去烧菜吧

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: AntiLeaf

题目描述

烧菜

你有 m 种物品,第 i 种物品的大小为 a_i ,数量为 b_i b_i=0 表示有无限个)。
你还有 n 个背包,体积分别为 1 n ,现在你很想知道用这些物品填满某个背包的方案数。
为了满足你的好奇心,你决定把填满每个背包的方案数都算一遍。
因为你其实只是闲得无聊,所以你只想知道方案数对 998244353 7\times 17\times 2^{23}+1 ,一个质数)取模后的值。

输入格式

第一行两个非负整数,分别表示 n,m
以下 m 行,每行两个非负整数,分别表示 a_i,b_i

输出格式

输出 n 个非负整数表示答案。

样例

样例输入

5 3
1 0
1 1
3 2

样例输出

2
2
3
4
4

样例解释

拼出 1 ~ 5 的方案分别如下:
\{1_1\},\{1_2\}
\{1_1,1_1\},\{1_1,1_2\}
\{1_1,1_1,1_1\},\{1_1,1_1,1_2\},\{3\}
\{1_1,1_1,1_1,1_1\},\{1_1,1_1,1_1,1_2\},\{1_1,3\},\{1_2,3\}
\{1_1,1_1,1_1,1_1,1_1\},\{1_1,1_1,1_1,1_1,1_2\},\{1_1,1_1,3\},\{1_1,1_2,3\}

数据范围与提示

0< n,m\le 10^5, 0\le a_i\le 110000,0\le b_i\le 10^6