나니와즈 군은 섣달그믐 음악 프로그램에서 전통적인 켄다마 챌린지에 도전하려고 합니다. 만약 최소 $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

입력 2

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

출력 2

1

입력 3

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

출력 3

62790646

참고

첫 번째 예제에 대하여: 선수 $i$가 성공하는 사건을 $S$, 실패하는 사건을 $F$라고 합시다. 가능한 패턴과 그 확률은 다음과 같습니다.

• $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$을 출력합니다.

두 번째 예제에 대하여: 마지막에 수행하는 나니와즈 군의 실력이 좋지 않더라도, 조력자들이 믿음직하다면 괜찮습니다.

확률의 $998244353$ 모듈로 정의

요구되는 확률은 항상 유리수임이 증명될 수 있습니다. 이 문제의 제약 조건 하에서, 확률을 기약 분수 $\frac{y}{x}$로 나타낼 때 $x$는 $998244353$으로 나누어떨어지지 않음이 보장됩니다.

이 경우, $xz \equiv y \pmod{998244353}$을 만족하는 유일한 정수 $z$($0 \le z \le 998244352$)가 존재합니다. 이 $z$를 출력하세요.