「RiOI-03」3-2
题目背景
> Heart beat to death[.](https://www.luogu.com.cn/problem/P9304)
题目描述
给定一个正整数 $n$。将 $[0,2^n)$ 中每个整数的二进制最低 $n$ 位**从低到高**依次写在一个 $2^n\times n$ 的矩阵上。**矩阵两维的下标都从 $0$ 开始。** 如，当 $n=3$ 时，矩阵是这样的：
给定 $q$ 次询问，每次询问这个矩阵下标为 $(x,y)$ 的格子所在的四连通块大小对 $998244353$ 取模的值。
输入输出格式
输入格式
第一行两个正整数 $n,q$。
接下来 $q$ 行，每行两个非负整数 $x,y$，表示一次询问。
输出格式
输出 $q$ 行，每行一个正整数，表示每次询问答案对 $998244353$ 取模的值。
输入输出样例
输入样例 #1
2 2
1 1
2 0输出样例 #1
3
1说明
#### 【样例 #1 解释】
图为 $n=2$ 时的矩阵，其中同一个颜色的为一个四连通块。
***
#### 【数据范围】
**本题开启捆绑测试。**
| $\text{SubTask}$ | 分值 | $n\le$ | $q\le$ |
| :----------: | :----------: | :----------: | :----------: |
| $0$ | $5$ | $15$ | $15$ |
| $1$ | $20$ | $15$ | $5\times 10^5$ |
| $2$ | $25$ | $5\times 10^3$ | $5\times 10^3$ |
| $3$ | $50$ | $10^{18}$ | $5\times 10^5$ |
对于 $100\%$ 的数据，$0\le y\lt n\le 10^{18}$，$0\le x\lt \min(2^n, 10^{18})$，$1\le q\le 5\times 10^5$。
**请选用较快的输入输出方式。**