题目背景

小 Atom 经过一个月的 Codeforces 历练，磨练出一身本领，终于迎来了正式比赛。然而，命运似乎仍未放过他……

题目描述

由于某些特殊且不可言说的原因，小 Atom 被迫要翘掉 $k$ 节 E 先生的课程。这些特殊事件的发生时间是随机的，对小 Atom 来说，每节课是否被迫翘课的概率是相等的，但他已知总共需要翘课 $k$ 节。

小 Atom 通过预测模型得知每节课被 E 先生点名的概率为 $p_i$。现在，他想知道，在他翘课的情况下，被 E 先生点名但自己不在场的期望次数是多少（结果需要对 $998244353$ 取模）。

输入格式

共 $n+1$ 行。

• 第一行包含两个正整数 $n$ 和 $k$，表示课程总数和小 Atom 需要翘掉的课程数量。
• 接下来的 $n$ 行中，每行包含两个整数 $a_i$ 和 $b_i$，表示第 $i$ 节课被 E 先生点名的概率 $p_i = \frac{a_i}{b_i}$。

输出格式

输出一个整数，表示小 Atom 被点名但不在场的期望次数，对 $998244353$ 取模。

样例 #1

样例输入 #1

3 1
0 1
0 1
6 6

样例输出 #1

332748118

样例解释

有 3 节课，小 Atom 需要翘 1 节课，因此每节课被迫翘掉的概率都是 $\frac{1}{3}$，每节课的点名概率分别为 $0,0,1$。

因此被发现的情况就是正好翘第 $3$ 节课，概率为 $\frac{1}{3} \times 1=\frac{1}{3}$。

$\frac{1}{3}$ 在模 $998244353$ 意义下表示为 $332748118$。

提示

• $1 \leq k \leq n \leq 5 \times 10^5$
• $0 \leq a_i \leq b_i \leq 10^6$，且保证 $b_i \neq 0$

在模 $998244353$ 意义下，$\frac{a}{b}$ 可以表示为 $a \times b^{-1}$，其中 $b^{-1}$ 是 $b$ 在模 $998244353$ 意义下的逆元。

提示： 费马小定理是数论中的一个重要工具。对于质数 $p$，如果整数 $a$ 不是 $p$ 的倍数，则有 $a^{p-1} \equiv 1 \pmod{p}$。这意味着 $a \times a^{p-2} \equiv 1 \pmod{p}$，所以 $a^{p-2}$ 是 $a$ 在模 $p$ 意义下的逆元。