给定三个整数 $N$、$M$ 和 $K$，考虑所有具有 $N$ 个顶点的无标号有根树，满足其中恰好有 $M$ 个顶点拥有 $K$ 个子节点。设 $A(N, M, K)$ 为在考虑每个顶点的子节点顺序（即子节点是有序的）时，满足上述条件的树的数量。

形式化地，如果两棵树的根节点子节点数量不同，或者存在一个数 $t$ 使得两棵树的第 $t$ 个子节点所对应的子树不同，则认为这两棵树是不同的。

现在给定一个整数 $N$ 和 $Q$ 对 $(M_1, K_1), \dots, (M_Q, K_Q)$。求 $A(N, M_1, K_1), \dots, A(N, M_Q, K_Q)$ 的值。

由于结果可能很大，输出答案模 $998\,244\,353$ 的余数。

输入格式

第一行包含两个整数 $N$ 和 $Q$（$1 \le N \le 10^5$，$1 \le Q \le 10^6$）。

接下来的 $Q$ 行，每行包含两个整数；第 $i$ 行包含两个整数 $M_i$ 和 $K_i$。保证 $0 \le M_i, K_i \le N$。

输出格式

输出 $Q$ 行；第 $i$ 行包含一个整数，表示 $A(N, M_i, K_i)$ 模 $998\,244\,353$ 的值。

样例

输入样例 1

1 1
1 0

输出样例 1

1

输入样例 2

5 10
4 1
0 0
1 2
4 0
1 3
1 4
3 0
3 1
0 5
0 1

输出样例 2

1
0
6
1
4
1
6
0
14
3