该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

聪聪在一次睡觉时来到了梦境中的世界。

梦里，他处在一个 $n\times n$ 的网格中，这里一共有 $n\times n$ 个格子，排成 $n$ 行 $n$ 列，行和列的编号都从 $1$ 开始。

因为聪聪太喜欢组合数学了，所以他在梦里都在研究组合数学。

他想到了这样一个问题：

假设他一开始处在坐标 $(x,y)$ 处的格子，然后从这里开始进行一次旅行：

（1）每一刻，他只能朝上下左右四个方向之中的某个方向走一格，但不能走出这个网格；或者是在此时结束本次旅行。

（2）如果他曾经朝上方走过，那么在未来任何一刻都不能朝下走，同理，朝下走过未来也不能朝上走，左右也同理。

举个例子：假设这是一个 $5\times 5$ 的网格，聪聪从 $(3,4)$ 出发旅行，以下是一些合理的旅游路线：

（1）直接在 $(3,4)$ 结束旅行。

（2）$(3,4)->(4,4)->(5,4)->(5,3)->(5,2)$ 然后在 $(5,2)$ 结束旅行。

（3）$(3,4)->(3,3)->(2,3)->(1,3)->(1,2)$，然后在 $(1,2)$ 结束旅行。

（4）$(3,4)->(2,4)->(1,4)->(1,3)->(1,2)$，然后在 $(1,2)$ 结束旅行。

但是，形如 $(3,4)->(2,4)->(2,3)->(3,3)$ 这样的路线是不合理的，因为他在向上（$(3,4)->(2,4)$）走过后，又向下（$(2,3)->(3,3)$）走过。

聪聪给了你 $q$ 个问题，每个问题给你 $(x,y)$，你需要帮聪聪算一下，聪聪从 $(x,y)$ 出发，有多少种合法的旅行路线。

输入格式

第一行输入 $n,q$。

接下来 $q$ 行，每行两个数字 $(x,y)$ 表示一次询问。

输出格式

对于每次询问，输出答案 $\mod 998244353$ 在单独的一行。

样例输入 #1

2 3
1 1
1 2
2 2

样例输出 #1

5
5
5

样例解释 #1

比如从 $(1,1)$ 出发，有下列 $5$ 种路线：

(1,1)

(1,1),(1,2)

(1,1),(2,1)

(1,1),(1,2),(2,2)

(1,1),(2,1),(2,2)

样例输入 #2

10 5
1 1
2 5
5 2
6 7
7 9

样例输出 #2

184755
7031
7031
2819
12181

下发文件

数据范围

本题共 20 个测试点。

对于100%的数据：$1\leq n\leq 10^6,1\leq q\leq 10^{5},1\leq x,y\leq n$。