← 返回题目列表

AtCoder · abc199_e

E. 排列

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

分数: 500 点

问题陈述

打印序列数 a 是以下排列 (1, 2, 3, \dots, N) 并满足以下条件:

  • 对于每个整数 i 这样 1 \le i \le M,最多 Z_i 中的数字 a_1, a_2, a_3, \dots, a_{X_i} 小于或等于 Y_i .

约束

  • 2 \le N \le 18
  • 0 \le M \le 100
  • 1 \le X_i \lt N
  • 1 \le Y_i \lt N
  • 0 \le Z_i \lt N
  • 输入中的所有值都是整数。

输入

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

N M
X_1 Y_1 Z_1
X_2 Y_2 Z_2
X_3 Y_3 Z_3
\hspace{23pt} \vdots
X_M Y_M Z_M

输出

打印答案。


示例输入 1

3 1
2 2 1

示例输出 1

4

四个序列 a 满足条件是:

  • (1, 3, 2)
  • (2, 3, 1)
  • (3, 1, 2)
  • (3, 2, 1)

(1, 2, 3) 和 (2, 1, 3) 违反条件,因为它们每个都有两个小于或等于 2 其中 a_1, a_2.


示例输入 2

5 2
3 3 2
4 4 3

示例输出 2

90

示例输入 3

18 0

示例输出 3

6402373705728000