سيخوض نانيوازو-كون تحدي الكينداما التقليدي في برنامج موسيقي ليلة رأس السنة. إذا نجح $K$ أشخاص على الأقل بشكل متتالٍ، فسيتم تحطيم الرقم القياسي. ولتعظيم احتمال النجاح قدر الإمكان، قرر خوض التحدي بفريق مكون من $N$ لاعبين تم اختيارهم بعناية.
سيحاول اللاعبون الـ $N$ لعب الكينداما بالترتيب من الأول ($1$) إلى الـ $N$. احتمال نجاح اللاعب رقم $i$ ($1 \le i \le N$) هو $\frac{A_i}{B_i}$، ونجاح أو فشل كل لاعب مستقل عن الآخرين.
أوجد احتمال وجود مقطع واحد على الأقل ينجح فيه $K$ أو أكثر من اللاعبين المتتاليين، بباقي القسمة على $998244353$.
Input
في السطر الأول، يُعطى العددان الصحيحان $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$)
Output
اطبع الاحتمال بباقي القسمة على $998244353$ في سطر واحد.
Examples
Input 1
2 2 1 1 1 2
Output 1
499122177
Input 2
5 4 1 1 1 1 1 1 1 1 1 10000
Output 2
1
Input 3
5 3 3 14 1 59 2 65 3 58 9 79
Output 3
62790646
Note
بالنسبة للمثال الأول: ليكن $\text{S}$ يمثل حدث نجاح اللاعب $i$، و $\text{F}$ يمثل حدث فشل اللاعب $i$. الأنماط الممكنة واحتمالاتها هي كما يلي:
- $\text{SS} : 1 \times \frac{1}{2} = \frac{1}{2}$
- $\text{SF} : 1 \times \frac{1}{2} = \frac{1}{2}$
فقط $\text{SS}$ يحتوي على مقطع ينجح فيه لاعبان ($2$) على الأقل بشكل متتالٍ، واحتماله هو $\frac{1}{2}$. بما أن $499122177 \times 2 \equiv 1 \pmod{998244353}$، اطبع $499122177$.
بالنسبة للمثال الثاني: حتى لو لم يكن نانيوازو-كون، الذي يؤدي في النهاية، ماهرًا جدًا، فلا بأس طالما أن المساعدين موثوقون.
تعريف الاحتمال بباقي القسمة على $998244353$
يمكن إثبات أن الاحتمال المطلوب هو دائمًا عدد كسري. تحت قيود هذه المسألة، عندما يُعبَّر عن الاحتمال ككسر مختزل $\frac{y}{x}$، فمن المضمون أن $x$ لا يقبل القسمة على $998244353$.
في هذه الحالة، يوجد عدد صحيح وحيد $z$ يحقق $0 \le z \le 998244352$ بحيث يكون $xz \equiv y \pmod{998244353}$. اطبع هذا العدد $z$.