分数: 900 点
问题陈述
在这个问题中,我们简单地调用一棵树 N 顶点编号 1,2,\ldots,N 和未编号的边 N- 顶点树。
当 N- 顶点树 T 和排列 Q=(Q_1,Q_2,\ldots,Q_N) of (1,2,\ldots,N) 满足以下条件,则排列 Q 被称为 良好的排列 树的 树的 T:
有 N 点 1,2,\ldots,N 按此顺序逆时针等间隔排列在圆上。对于每条边 \lbrace u,v\rbrace 树的 T,画一条连接两点的线段 Q_u,Q_v。那么,其中 N-1 绘制的线段,除了端点之外,没有两条线段有公共点。
你被给予 M 的排列 (1,2,\ldots,N): P^1=(P^1_1,P^1_2,\ldots,P^1_N),P^2=(P^2_1,P^2_2,\ldots,P^2_N),\ldots,P^M=(P^M_1,P^M_2,\ldots,P^M_N).
求模数 998244353,属于 N- 顶点树使得 P^1,P^2,\ldots,P^M 都是很好的排列。
约束
- 2\leq N,M\leq 500
- P^1,P^2,\ldots,P^M 是排列 (1,2,\ldots,N).
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M P^1_1 P^1_2 \ldots P^1_N P^2_1 P^2_2 \ldots P^2_N \vdots P^M_1 P^M_2 \ldots P^M_N
输出
输出数字,模数 998244353,属于 N- 顶点树使得 P^1,P^2,\ldots,P^M 都是很好的排列。
示例输入 1
4 2 1 4 2 3 3 1 4 2
示例输出 1
8
例如,对于以下两棵树,都 P^1,P^2 是很好的排列。 (蓝色数字代表顶点编号。)

另一方面,对于以下树, P^2 不是一个好的排列。

有 8 总共四个顶点树,使得两个 P^1,P^2 是很好的排列。
示例输入 2
12 3 7 9 1 10 8 12 2 6 11 5 4 3 8 10 4 12 11 7 6 3 1 2 9 5 10 4 9 7 5 1 3 11 8 12 6 2
示例输出 2
540