Consider a multiset of $n$ elements where each number in the set is of the form $2^i$ ($i \in (-\infty, 0] \cap \mathbb{Z}$). How many such multisets exist such that the sum of all numbers in the set equals $k$? You only need to output the answer modulo $998244353$.
Input
The first line contains two positive integers $N$ and $Q$, representing the range of $n$ and the number of queries.
The next $Q$ lines each contain two positive integers $n$ and $k$, with the guarantee that $n \ge k$.
Output
Output $Q$ lines, each containing an integer representing the number of ways modulo $998244353$.
Examples
Input 1
3000000 10 4 1 4 2 4 3 4 4 10 3 100 13 1000 666 100000 99824 1000000 112358 3000000 2999990
Output 1
2 2 1 1 35 69549003 511129129 673402331 520502118 253
Subtasks
For $100\%$ of the data, it is guaranteed that $1\le k\le n\le N\le 3\times 10^6$ and $Q\le 2\times 10^5$.
| Data Point ID | Special Constraints |
|---|---|
| $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$ |