题目描述

有一块由 $n$ 个格子组成的画布，你要将它的每个格子涂成 $m$ 种颜色之一，并满足 $k$ 个限制条件。

第 $i$ 个限制条件形如 $(l_i, r_i)$，含义是：至少有一种颜色在第 $l_i$ 至第 $r_i$ 个格子中出现至少两次。

计数有多少种合法的染色方案，答案对 $10^9 + 7$ 取模。

输入格式

第一行三个正整数 $n, m, k$。
接下来 $k$ 行，每行两个正整数 $l_i, r_i$。

输出格式

一行一个正整数，表示答案对 $10^9 + 7$ 取模后的结果。

5 2 4
1 2
2 3
4 5
1 5

4

数据范围与提示

• 对于所有数据：$1 \le n, m \le 10^6$，$1 \le k \le 2000$。
• 测试点 1：$1 \le n, m, k \le 7$。
• 测试点 2～3：$1 \le n \le 7$，$1 \le m \le 100$，$1 \le k \le 10$。
• 测试点 4～5：$1 \le n, m \le 100$，$1 \le k \le 10$。
• 测试点 6～7：$1 \le n, m \le 2000$，$1 \le k \le 100$。
• 测试点 8～10：无特殊限制。