#P11767. 「KFCOI Round #1」缥缈

    ID: 12778 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>洛谷原创O2优化组合数学洛谷比赛

「KFCOI Round #1」缥缈

题目背景

这个世界这么大,是机缘让我们相遇,也是机缘促使我们分开。

是爱情促使我们沉沦,也是爱情让我们形同陌路。

在这一路上,为什么就刚好喜欢上你呢?

题目描述

你需要求出满足如下条件的长度为 mm 的序列 BB 的个数:

  • BB 中全为正整数。
  • BB 中不包含 xx
  • BB 中元素两两不同。
  • BB 中元素在范围 [1,n][1,n] 中。
  • BB 中任意两个元素相差不会超过 tt

qq 次询问,每次给出 xxtt

由于结果可能很大,输出答案对 109+710^9+7 取余的结果。

输入格式

本题输入均为正整数。

第一行三个数 n,m,qn,m,q

接下来 qq 行,每行两个数 x,tx,t 代表一个询问。

输出格式

输出 qq 行,每行一个数,第 ii 行代表第 ii 次询问的答案对 109+710^9+7 取余的结果。

6 3 3
1 3
2 3
3 5
42
30
60
10 7 5
3 9
8 6
5 7
9 6
10 7
181440
5040
15120
10080
75600

提示

数据范围

本题采用捆绑测试

  • Subtask 1(10 points):n12n \le 12m7m\le 7q10q\le 10
  • Subtask 2(15 points):n2000n \le 2000m=2m=2q2000q\le 2000
  • Subtask 3(15 points):m=2m=2
  • Subtask 4(20 points):xtx\le t
  • Subtask 5(40 points):无特殊限制。

对于所有测试数据,2n2×1052\le n \le 2 \times 10 ^52mn2 \le m \le n1xn1 \le x \le nm1t<nm - 1\le t < n1q2×1051 \le q \le 2\times 10^5