Rozważmy wszystkie multizbiory składające się z $n$ elementów, gdzie każda liczba w zbiorze jest postaci $2^i$ dla $i \in (-\infty, 0] \cap \mathbb{Z}$. Ile istnieje takich zbiorów, których suma elementów wynosi $k$? Odpowiedź należy podać modulo $998244353$.
Wejście
W pierwszej linii znajdują się dwie liczby całkowite dodatnie $N, Q$, oznaczające zakres $n$ oraz liczbę zapytań.
W kolejnych $Q$ liniach znajdują się dwie liczby całkowite dodatnie $n, k$, przy czym gwarantuje się, że $n \ge k$.
Wyjście
Wypisz $Q$ linii, z których każda zawiera jedną liczbę całkowitą będącą liczbą sposobów modulo $998244353$.
Przykład
Przykład 1
Wejście
3000000 10 4 1 4 2 4 3 4 4 10 3 100 13 1000 666 100000 99824 1000000 112358 3000000 2999990
Wyjście
2 2 1 1 35 69549003 511129129 673402331 520502118 253
Podzadania
Dla $100\%$ danych wejściowych gwarantuje się, że $1\le k\le n\le N\le 3\times 10^6$ oraz $Q\le 2\times 10^5$.
| Numer podzadania | Ograniczenia dodatkowe |
|---|---|
| $1, 2$ | $N=10$ |
| $3, 4$ | $N=5\times 10^3$ |
| $5, 6$ | $Q=1, N=10^5$ |
| $7$ | $Q=1$ |
| $8$ | $N=10^5$ |
| $9, 10$ |