Naniwazu-kun sẽ tham gia thử thách kendama truyền thống trong một chương trình âm nhạc đêm giao thừa. Nếu có ít nhất $K$ người liên tiếp thành công, kỷ lục sẽ bị phá vỡ. Để tối đa hóa xác suất thành công, cậu ấy quyết định thực hiện thử thách với một đội gồm $N$ người chơi được lựa chọn cẩn thận.
$N$ người chơi sẽ thực hiện kendama theo thứ tự từ người thứ 1 đến người thứ $N$. Xác suất người chơi thứ $i$ ($1 \le i \le N$) thành công là $\frac{A_i}{B_i}$, và kết quả thành công hay thất bại của mỗi người chơi là độc lập.
Hãy tìm xác suất để tồn tại ít nhất một đoạn gồm $K$ người chơi liên tiếp trở lên thành công, theo modulo 998244353.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên $N, K$ cách nhau bởi dấu cách ($1 \le K \le N \le 2 \times 10^5$).
Trong $N$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $A_i, B_i$ cách nhau bởi dấu cách ($1 \le A_i \le B_i \le 998244352$).
Dữ liệu ra
In ra xác suất theo modulo 998244353 trên một dòng duy nhất.
Ví dụ
Dữ liệu vào 1
2 2 1 1 1 2
Dữ liệu ra 1
499122177
Ghi chú
Đối với ví dụ đầu tiên: Gọi S là sự kiện người chơi $i$ thành công, và F là sự kiện người chơi $i$ thất bại. Các mẫu có thể xảy ra và xác suất tương ứng như sau:
- SS : $1 \times \frac{1}{2} = \frac{1}{2}$
- SF : $1 \times \frac{1}{2} = \frac{1}{2}$
Chỉ có SS chứa một đoạn mà ít nhất 2 người chơi liên tiếp thành công, và xác suất của nó là $\frac{1}{2}$. Vì $499122177 \times 2 \equiv 1 \pmod{998244353}$, kết quả in ra là 499122177.
Dữ liệu vào 2
5 4 1 1 1 1 1 1 1 1 1 10000
Dữ liệu ra 2
1
Ghi chú
Đối với ví dụ thứ hai: Ngay cả khi Naniwazu-kun, người thực hiện cuối cùng, không quá khéo léo, thì vẫn ổn miễn là những người hỗ trợ đáng tin cậy.
Dữ liệu vào 3
5 3 3 14 1 59 2 65 3 58 9 79
Dữ liệu ra 3
62790646
Ghi chú
Đối với ví dụ đầu tiên: Gọi S là sự kiện người chơi $i$ thành công, và F là sự kiện người chơi $i$ thất bại. Các mẫu có thể xảy ra và xác suất tương ứng như sau:
- SS : $1 \times \frac{1}{2} = \frac{1}{2}$
- SF : $1 \times \frac{1}{2} = \frac{1}{2}$
Chỉ có SS chứa một đoạn mà ít nhất 2 người chơi liên tiếp thành công, và xác suất của nó là $\frac{1}{2}$. Vì $499122177 \times 2 \equiv 1 \pmod{998244353}$, kết quả in ra là 499122177.
Đối với ví dụ thứ hai: Ngay cả khi Naniwazu-kun, người thực hiện cuối cùng, không quá khéo léo, thì vẫn ổn miễn là những người hỗ trợ đáng tin cậy.
Định nghĩa xác suất modulo 998244353
Có thể chứng minh rằng xác suất cần tìm luôn là một số hữu tỉ. Với các ràng buộc của bài toán này, khi xác suất được biểu diễn dưới dạng phân số tối giản $\frac{y}{x}$, đảm bảo rằng $x$ không chia hết cho 998244353.
Trong trường hợp này, tồn tại duy nhất một số nguyên $z$ với $0 \le z \le 998244352$ sao cho $xz \equiv y \pmod{998244353}$. Hãy in ra số $z$ này.