题目描述

给定一个有 $N$ 个顶点、$M$ 条边的简单有向图，顶点编号为 $1$ 到 $N$。第 $i$ 条边从顶点 $u_i$ 指向顶点 $v_i$。

保证该图中不存在有向环。

求从顶点 $1$ 到顶点 $N$ 的路径条数，对 $998244353$ 取模。

共有 $T$ 组测试数据，请分别求解。

限制条件

• $1\le T\le 10^5$
• $2\le N\le 2\times 10^5$
• $0\le M\le \min\left(\dfrac{N(N-1)}2,2\times 10^5\right)$
• $1\le u_i,v_i\le N$
• 当 $i\ne j$ 时，$(u_i,v_i)\ne(u_j,v_j)$
• 输入图为不含有向环的简单有向图。
• 所有测试数据中 $N$ 的总和不超过 $2\times 10^5$。
• 所有测试数据中 $M$ 的总和不超过 $2\times 10^5$。
• 所有输入均为整数。

输入

输入通过标准输入按以下格式给出：

T
case_1
case_2
...
case_T

每组测试数据的格式如下：

N M
u_1 v_1
u_2 v_2
...
u_M v_M

输出

输出 $T$ 行。第 $i$ 行输出第 $i$ 组测试数据的答案，即从顶点 $1$ 到顶点 $N$ 的路径条数对 $998244353$ 取模后的结果。

样例输入 1

3
4 4
1 2
2 3
3 4
2 4
5 4
1 2
2 3
4 5
1 3
7 18
1 6
1 4
6 4
6 3
4 3
1 5
6 5
4 5
3 5
1 2
6 2
4 2
3 2
5 2
6 7
4 7
5 7
2 7

样例输出 1

2
0
24

对于第一组测试数据，从顶点 $1$ 到顶点 $4$ 的路径有以下两条：

• $1\to2\to3\to4$
• $1\to2\to4$