В ряд расположено \(n\) мешков, пронумерованных от \(1\) до \(n\); \(i\)-й мешок содержит \(a_i\) золотых монет и \(b_i\) серебряных монет.
Ценность золотой монеты равна \(1\). Ценность серебряной монеты равна \(0\) или \(1\), и определяется для каждой серебряной монеты независимо (\(0\) с вероятностью \(\frac{1}{2}\) и \(1\) с вероятностью \(\frac{1}{2}\)).
Вам нужно ответить на \(q\) независимых запросов. Каждый запрос имеет следующий формат:
- \(l\) \(r\) — посчитайте вероятность того, что суммарная ценность монет в мешках с \(l\) по \(r\) строго больше суммарной ценности во всех остальных мешках.
Выходные данные
Для каждого запроса выведите одно целое число — вероятность того, что суммарная ценность монет в мешках с \(l\) по \(r\) строго больше суммарной ценности во всех остальных мешках, взятое по модулю \(998244353\).
Вероятность можно выразить в виде несократимой дроби \(\frac{x}{y}\). Вы должны вывести значение \(x \cdot y^{-1} \bmod 998244353\), где \(y^{-1}\) — целое число, такое, что \(y \cdot y^{-1} \bmod 998244353 = 1\).
Примечание
В обоих запросах из первого примера ответ равен \(\frac{1}{4}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
1 0
0 2
2 2
1 1
|
748683265 748683265
|
|
2
|
4 3
2 3 4 5
1 0 7 3
3 3
2 3
1 4
|
997756929 273932289 1
|