#P13953. [2024多校联盟省选模拟]染色

    ID: 13165 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200动态规划组合数学排序计数DP前缀和

[2024多校联盟省选模拟]染色

题目描述

有一块由 nn 个格子组成的画布,你要将它的每个格子涂成 mm 种颜色之一,并满足 kk 个限制条件。

第 ii 个限制条件形如 (li,ri)(l_i, r_i),含义是:至少有一种颜色在第 lil_i 至第 rir_i 个格子中出现至少两次。

计数有多少种合法的染色方案,答案对 109+710^9 + 7 取模。

输入格式

第一行三个正整数 n,m,kn, m, k。
接下来 kk 行,每行两个正整数 li,ril_i, r_i。

输出格式

一行一个正整数,表示答案对 109+710^9 + 7 取模后的结果。

5 2 4
1 2
2 3
4 5
1 5
4

数据范围与提示

  • 对于所有数据:1≤n,m≤1061 \le n, m \le 10^6,1≤k≤20001 \le k \le 2000。
  • 测试点 1:1≤n,m,k≤71 \le n, m, k \le 7。
  • 测试点 2~3:1≤n≤71 \le n \le 7,1≤m≤1001 \le m \le 100,1≤k≤101 \le k \le 10。
  • 测试点 4~5:1≤n,m≤1001 \le n, m \le 100,1≤k≤101 \le k \le 10。
  • 测试点 6~7:1≤n,m≤20001 \le n, m \le 2000,1≤k≤1001 \le k \le 100。
  • 测试点 8~10:无特殊限制。