Naniwazu-kun va relever le défi traditionnel du kendama lors d'une émission musicale du Nouvel An. Si au moins $K$ personnes réussissent consécutivement, le record sera battu. Pour maximiser autant que possible la probabilité de succès, il a décidé de relever le défi avec une équipe de $N$ joueurs soigneusement sélectionnés.

Les $N$ joueurs tenteront le kendama dans l'ordre, du 1-er au $N$-ième. La probabilité que le $i$-ième joueur ($1 \le i \le N$) réussisse est $\frac{A_i}{B_i}$, et la réussite ou l'échec de chaque joueur est indépendant.

Trouvez la probabilité qu'il existe au moins un segment où $K$ joueurs consécutifs ou plus réussissent, modulo 998244353.

Entrée

Sur la première ligne, les entiers $N, K$ sont donnés séparés par un espace. ($1 \le K \le N \le 2 \times 10^5$)

Dans les $N$ lignes suivantes, la $i$-ième ligne contient les entiers $A_i, B_i$ séparés par un espace. ($1 \le A_i \le B_i \le 998244352$)

Sortie

Affichez la probabilité modulo 998244353 sur une seule ligne.

Exemples

Entrée 1

2 2
1 1
1 2

Sortie 1

499122177

Remarque

Pour le premier exemple :

Soit S l'événement où le joueur $i$ réussit, et F l'événement où le joueur $i$ échoue. Les motifs possibles et leurs probabilités sont les suivants :

• SS : $1 \times \frac{1}{2} = \frac{1}{2}$
• SF : $1 \times \frac{1}{2} = \frac{1}{2}$

Seul SS contient un segment où au moins 2 joueurs réussissent consécutivement, et sa probabilité est $\frac{1}{2}$. Puisque $499122177 \times 2 \equiv 1 \pmod{998244353}$, affichez 499122177.

Entrée 2

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

Sortie 2

1

Remarque

Pour le deuxième exemple :

Même si Naniwazu-kun, qui passe en dernier, n'est pas très doué, ce n'est pas grave tant que les assistants sont fiables.

Entrée 3

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

Sortie 3

62790646

Définition de la probabilité modulo 998244353

Il peut être prouvé que la probabilité requise est toujours un nombre rationnel. Sous les contraintes de ce problème, lorsque la probabilité est exprimée sous la forme d'une fraction irréductible $\frac{y}{x}$, il est garanti que $x$ n'est pas divisible par 998244353.

Dans ce cas, il existe un unique entier $z$ tel que $0 \le z \le 998244352$ et $xz \equiv y \pmod{998244353}$. Affichez ce $z$.