题目描述

打印满足以下条件的序列 $a$ 的数量，其中 $a$ 是 $(1, 2, 3, \dots, N)$ 的排列：

• 对于每个满足 $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 < N$
• $1 \le Y_i < N$
• $0 \le Z_i < 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$。

示例输入 2

5 2
3 3 2
4 4 3

示例输出 2

90

示例输入 3

18 0

示例输出 3

6402373705728000