Battle Rally Minimization

A battle lasts for \(n\) time moments. In the \(i\)-th moment, the moment is safe with probability \(\frac{x_i}{x_i+y_i}\). Only in a safe moment you can perform a "rally". You are given an integer \(a\) and \(b\). The rule is that in every contiguous block of \(a\) time moments, there must be at least \(b\) moments in which a rally is performed. Under this constraint, you wish to minimize the total number of rallies. If it is impossible to satisfy the constraint for a given outcome, the number of rallies for that outcome is defined to be \(0\).

Your task is to compute the expected (minimized) number of rallies over all random outcomes, where the answer is taken modulo \(998244353\).

Note: All probabilities are independent, and all arithmetic with fractions should be performed in \(\mathrm{mod}\;998244353\) with appropriate modular inverses.

inputFormat

The first line contains three integers \(n\), \(a\), and \(b\), where \(1 \le n \le \) (small value, e.g. 15) and \(1 \le b \le a \le n\).

Then follow \(n\) lines. The \(i\)-th of these lines contains two integers \(x_i\) and \(y_i\) (with \(x_i,y_i>0\)). The probability that the \(i\)-th moment is safe is \(\frac{x_i}{x_i+y_i}\).

outputFormat

Output a single integer, which is the expected minimal number of rallies modulo \(998244353\).

sample

3 2 1
1 1
1 1
1 1

747244356