Cho \(N\) biến cố độc lập \(X_1, X_2, \dots, X_N\). Biến cố thứ \(i\) diễn ra với xác suất \(p_i = \frac{a_i}{b_i}\).

Xét biến ngẫu nhiên \(X = \sum_{i=1}^N X_i\) đại diện cho tổng số biến cố xảy ra (trong đó \(X_i = 1\) nếu biến cố \(i\) xảy ra và \(X_i = 0\) nếu không xảy ra).

Cho một số nguyên dương \(K\). Hãy tính giá trị kỳ vọng \(E[X^K] \pmod{998244353}\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(1 \le N \le 10^5, 1 \le K \le 2000\)).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i, b_i\) (\(0 \le a_i \le b_i < 998244353, b_i > 0\)), mô tả xác suất \(p_i = \frac{a_i}{b_i}\) xảy ra của biến cố \(i\).

Output

• In ra một số nguyên duy nhất là giá trị \(E[X^K] \pmod{998244353}\).

Example

2 2
1 2
1 2

499122177

Scoring

• Subtask 1 (100 điểm): \(1 \le N \le 10^5, 1 \le K \le 2000\).