C - Circular Tree Embedding Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 900 点

問題文

この問題では，頂点に 1,2,\ldots,N の番号が付けられ，辺に番号が付いていない N 頂点の木を単に N 頂点の木と呼ぶことにします．

N 頂点の木 T および (1,2,\ldots,N) の順列 Q=(Q_1,Q_2,\ldots,Q_N) が次の条件を満たすとき，順列 Q は木 T の 良い順列 であると呼びます．

円周上に N 個の点 1,2,\ldots,N がこの順で反時計回りに等間隔で配置されている．木 T の各辺 \lbrace u,v\rbrace に対して 2 点 Q_u,Q_v を結ぶ線分を書き込む．このとき，書き込まれた N-1 本の線分のうちどの 2 本を選んでも，それらは端点を除いて共有点を持たない．

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) が与えられます．

P^1,P^2,\ldots,P^M が全て良い順列となるような N 頂点の木の個数を 998244353 で割った余りを求めて下さい．

制約

  • 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

出力

P^1,P^2,\ldots,P^M が全て良い順列となるような N 頂点の木の個数を 998244353 で割った余りを出力せよ．

入力例 1

4 2
1 4 2 3
3 1 4 2

出力例 1

8

たとえば以下の 2 つの木に対して，P^1,P^2 はどちらも良い順列です．（青い数字は頂点番号を表しています．）

一方，以下の木に対して P^2 は良い順列ではありません．

P^1,P^2 がともに良い順列となるような 4 頂点の木は全部で 8 つあります．

入力例 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

Score : 900 points

Problem Statement

In this problem, we simply call a tree with N vertices numbered 1,2,\ldots,N and unnumbered edges an N-vertex tree.

When an N-vertex tree T and a permutation Q=(Q_1,Q_2,\ldots,Q_N) of (1,2,\ldots,N) satisfy the following condition, the permutation Q is called a good permutation of tree T:

There are N points 1,2,\ldots,N arranged counterclockwise at equal intervals on a circle in this order. For each edge \lbrace u,v\rbrace of tree T, draw a line segment connecting the two points Q_u,Q_v. Then, among the N-1 line segments drawn, no two of them have a common point except at their endpoints.

You are given M permutations of (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).

Find the number, modulo 998244353, of N-vertex trees such that P^1,P^2,\ldots,P^M are all good permutations.

Constraints

  • 2\leq N,M\leq 500
  • P^1,P^2,\ldots,P^M are permutations of (1,2,\ldots,N).
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Output the number, modulo 998244353, of N-vertex trees such that P^1,P^2,\ldots,P^M are all good permutations.

Sample Input 1

4 2
1 4 2 3
3 1 4 2

Sample Output 1

8

For example, for the following two trees, both P^1,P^2 are good permutations. (The blue numbers represent vertex numbers.)

On the other hand, for the following tree, P^2 is not a good permutation.

There are 8 four-vertex trees in total such that both P^1,P^2 are good permutations.

Sample Input 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

Sample Output 2

540