Pak Chanek 有一个有向无环图(没有任何循环的有向图),其中包含 $$$N$$$ 个顶点。顶点 $$$i$$$ 具有远离该顶点的 $$$S_i$$$ 边。顶点 $$$i$$$ 的第 $$$j$$$ 条边指向顶点 $$$L_{i,j}$$$,并且具有整数 $$$W_{i,j}$$$ ($$$0\leq W_{i,j}\leq1$$$)。关于图的另一个信息是,图的形状使得每个顶点都可以从顶点 $$$1$$$ 通过零个或多个有向边到达。
Pak Chanek 有一个数组 $$$Z$$$ 最初为空。
Pak Chanek 定义函数 dfs 如下:
请注意,该函数不会跟踪哪些顶点已被访问,因此每个顶点可以被处理多次。
假设 Pak Chanek 执行了 dfs(1) 一次。之后,Pak Chanek 将得到一个数组 $$$Z$$$,其中包含一些元素 $$$0$$$ 或 $$$1$$$。将数组 $$$Z$$$ 中的反转定义为一对索引 $$$(x, y)$$$ ($$$x < y$$$),使得 $$$Z_x > Z_y$$$。如果 Pak Chanek 执行 dfs(1) 一次,$$$Z$$$ 中有多少种不同的反转?由于答案可能非常大,因此输出对 $$$998\,244\,353$$$ 取模的答案。
输入
第一行包含一个整数 $$$N$$$ ($$$2 \leq N \leq 10^5$$$) — 图中的顶点数。以下行包含从顶点 $$$1$$$ 到顶点 $$$N$$$ 的每个顶点的描述。
每个顶点 $$$i$$$ 的第一行包含一个整数 $$$S_i$$$ ($$$0 \leq S_i \leq N-1$$$) — 远离顶点 $$$i$$$ 的边数。
每个顶点 $$$i$$$ 的接下来 $$$S_i$$$ 行的第 $$$j$$$ 包含两个整数 $$$L_{i,j}$$$ 和 $$$W_{i,j}$$$ ($$$1 \leq L_{i,j} \leq N$$$; $$$0 \leq W_{i,j} \leq 1$$$) — 一条远离顶点 $$$i$$$ 的边,指向顶点 $$$L_{i,j}$$$,并且具有整数 $$$W_{i,j}$$$。对于每个 $$$i$$$,$$$L_{i,1}$$$、$$$L_{i,2}$$$、...、$$$L_{i,S_i}$$$ 的值是成对不同的。
保证所有顶点的 $$$S_i$$$ 之和不超过 $$$2 \cdot 10^5$$$。图中没有循环。每个顶点都可以从顶点 $$$1$$$ 通过零个或多个有向边到达。
输出
一个整数,表示 Pak Chanek 执行 dfs(1) 一次时 $$$Z$$$ 中的反转次数。由于答案可能非常大,因此输出对 $$$998\,244\,353$$$ 取模的答案。
示例
输入 #1
5 2 4 0 3 1 0 1 2 0 2 3 1 5 1 0
输出 #1
4
注意
下面是图上的dfs(1)过程。
最后,$$$Z=[0,1,0,1,1,0]$$$。它的所有反转都是 $$$(2,3)$$$、$$$(2,6)$$$、$$$(4,6)$$$ 和 $$$(5,6)$$$。