考虑全体 $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$ |