Рассмотрим мультимножество из $n$ элементов, где каждое число в множестве имеет вид $2^i$ ($i\in (-\infty,0] \cap \mathbb Z$). Сколько существует таких множеств, сумма всех элементов которых равна $k$? Ответ выведите по модулю $998244353$.
Входные данные
В первой строке содержатся два целых положительных числа $N$ и $Q$, обозначающие ограничение на $n$ и количество запросов.
Далее следуют $Q$ строк, каждая из которых содержит два целых положительных числа $n$ и $k$, при этом гарантируется, что $n\ge k$.
Выходные данные
Выведите $Q$ строк, в каждой из которых содержится одно целое число — количество способов по модулю $998244353$.
Примеры
Пример 1
3000000 10 4 1 4 2 4 3 4 4 10 3 100 13 1000 666 100000 99824 1000000 112358 3000000 2999990
Выходные данные 1
2 2 1 1 35 69549003 511129129 673402331 520502118 253
Подзадачи
Для $100\%$ данных гарантируется, что $1\le k\le n\le N\le 3\times 10^6$ и $Q\le 2\times 10^5$.
| Номер подзадачи | Специальные ограничения |
|---|---|
| $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$ |