← 返回题目列表

AtCoder · agc056_b

B. 范围 Argmax

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

分数: 900 点

问题陈述

给定一个整数 N 和 M 整数对。 的 i- 第对是 (L_i,R_i).

求整数序列的个数 x=(x_1,x_2,\cdots,x_M) 可以按如下方式生成,取模 998244353.

  • 提供排列 p=(p_1,p_2,\cdots,p_N) of (1,2,\cdots,N).
  • 对于每个 i (1 \leq i \leq M),让 x_i 是其中最大元素的索引 p_{L_i},p_{L_i+1},\cdots,p_{R_i}。也就是说, \max(p_{L_i},p_{L_i+1},\cdots,p_{R_i})=p_{x_i}.

约束

  • 2 \leq N \leq 300
  • 1 \leq M \leq N(N-1)/2
  • 1 \leq L_i < R_i \leq N
  • (L_i,R_i) \neq (L_j,R_j) (i \neq j)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

输出

打印答案。


示例输入 1

3 2
1 2
1 3

示例输出 1

4

例如,对于 p=(2,1,3),我们将有 x=(1,3).

满足要求的四个序列是 x=(1,1),(1,3),(2,2),(2,3).


示例输入 2

6 3
1 2
3 4
5 6

示例输出 2

8

示例输入 3

10 10
8 10
5 8
5 7
2 5
1 7
4 5
5 9
2 8
7 8
3 9

示例输出 3

1060