Migrated from Lutece 3018 给你一瓶魔法药水

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

猫猫虫capoo最近找上了你。它希望你可以带它环游宇宙。可是你和它都只是地球上的生物，根本不能离开水和氧气存活。这时，你想到大魔法师波波王就在地球上的某个角落，他的魔法商店里有一种神奇的魔法药水，喝下去就不需要氧气，也不需要水，便可以抵御宇宙糟糕的环境。

波波王是一个奇怪的大魔法师，他的魔法药水单凭魔法币还不足以购买。由于波波王的法力高深，他可以在你进入魔法商店的那一刻就知道你身上魔法币的种类和数量。你身上的魔法币必须刚好可以凑出魔法药水的价格，并且你还得在有限的时间内答对一个问题，波波王才会把魔法药水卖给你。这个问题是，有多少种方法通过你身上的魔法币刚好凑出魔法药水的价格？

由于魔法药水的价格每天都不一样，你希望在出发前，假设你的魔法币的总额能够支付魔法药水，对于所有可能的价格（包括$0$），求出有多少种方法，通过你身上的魔法币刚好凑出魔法药水的价格。同时，每个魔法币都有一个编号，这个编号由于某种魔法每天都在变化。波波王性格古怪，有时同一种魔法币的编号相同，有时所有魔法币的编号都不同。两种方案不同当且仅当至少存在一种编号的魔法币出现在一个方案中，而不出现在另一个方案中。由于方案数可能会很多，因此每种方案数均对$998244353$取模。

Input

第一行两个整数$n$，$opt$，$n$表示你拥有的魔法币的种数，$opt=0$时表示同一种魔法币的编号相同，$opt=1$时表示所有魔法币的编号都不同。

接下来$n$行，每行两个整数$k_i$，$m_i$，表示有$k_i$个面值为$m_i$的魔法币。

Output

一行$1+\sum_{i=1}^n k_i·m_i$个整数，下标从$0$开始，第$j$个整数表示魔法药水价格为$j$时，通过你身上的魔法币刚好凑出魔法药水价格的方案数，对$998244353$取模。

Samples

2 0
2 1
1 2

1 1 2 1 1

Constraints

$\sum_{i=1}^n k_i·m_i\leq 10^5$. $m_i$互不相同。

Note

两种方案不同当且仅当至少存在一种编号的魔法币出现在一个方案中，而不出现在另一个方案中。

对于样例，有$2$张面额为$1$的魔法币，$1$张面额为$2$的魔法币。

当魔法药水价格为$0$时，有$1$种方案，即不选择任何魔法币；

当魔法药水价格为$1$时，有$1$种方案，即1；

当魔法药水价格为$2$时，有$2$种方案，分别为1+1以及2；

当魔法药水价格为$3$时，有$1$种方案，即1+2；

当魔法药水价格为$4$时，有$1$种方案，即1+1+2；

然而capoo没有告诉你，capoo并不在意宇宙的奇观，它只希望可以和你待在一起。

Resources

2023 UESTC ICPC Training for Math