← 返回题目列表

AtCoder · arc199_c

C. 圆形树嵌入

中文机器翻译题面 查看原题

分数: 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