[ARC176] C - Max Permutation

C - Max Permutation

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 700 分

题面

计算满足以下所有条件的排列 的数量，取模 ：

• .

限制条件

• 若 .

---

输入

从标准输入中以以下格式给定：

输出

输出答案。

---

输入样例 1

4 2
1 2 4
2 3 2

输出样例 1

2

满足条件的两个排列 是 和 。

---

输入样例 2

6 3
1 4 3
2 5 6
3 4 2

输出样例 2

8

---

输入样例 3

20 17
9 16 13
5 14 20
15 20 14
5 13 17
18 20 14
14 20 20
6 13 11
12 16 19
2 15 10
6 17 11
7 18 7
8 18 12
8 16 13
6 16 13
2 18 10
9 10 15
7 14 20

输出样例 3

1209600