Naniwazu-kun 准备参加除夕音乐节目中的传统剑玉挑战。如果至少有 $K$ 个人连续成功，记录就会被打破。为了尽可能提高成功的概率，他决定组建一支由 $N$ 名精心挑选的选手组成的队伍。

这 $N$ 名选手将按顺序从第 $1$ 位到第 $N$ 位进行剑玉挑战。第 $i$ 位选手（$1 \le i \le N$）成功的概率为 $\frac{A_i}{B_i}$，且每位选手的成功或失败是相互独立的。

求存在至少一段连续 $K$ 名或更多选手成功的概率，结果对 $998244353$ 取模。

输入格式

第一行包含两个整数 $N, K$，用空格分隔。（$1 \le K \le N \le 2 \times 10^5$）

接下来的 $N$ 行中，第 $i$ 行包含两个整数 $A_i, B_i$，用空格分隔。（$1 \le A_i \le B_i \le 998244352$）

输出格式

输出概率对 $998244353$ 取模的结果，占一行。

样例

输入格式 1

2 2
1 1
1 2

输出格式 1

499122177

说明

对于第一个样例： 设 $S$ 表示选手 $i$ 成功，$F$ 表示选手 $i$ 失败。 可能的模式及其概率如下： $SS : 1 \times \frac{1}{2} = \frac{1}{2}$ $SF : 1 \times \frac{1}{2} = \frac{1}{2}$

只有 $SS$ 包含至少 $2$ 名选手连续成功的片段，其概率为 $\frac{1}{2}$。 由于 $499122177 \times 2 \equiv 1 \pmod{998244353}$，输出 $499122177$。

输入格式 2

5 4
1 1
1 1
1 1
1 1
1 10000

输出格式 2

1

说明

对于第二个样例： 即使最后出场的 Naniwazu-kun 技术不太好，只要帮手们可靠，也是可以的。

输入格式 3

5 3
3 14
1 59
2 65
3 58
9 79

输出格式 3

62790646

概率对 998244353 取模的定义

可以证明，所求概率总是一个有理数。在本题的约束条件下，当概率表示为最简分数 $\frac{y}{x}$ 时，保证 $x$ 不能被 $998244353$ 整除。

在这种情况下，存在唯一的整数 $z$，满足 $0 \le z \le 998244352$ 且 $xz \equiv y \pmod{998244353}$。 输出这个 $z$。