#PQJ985x4558. QOJ 985_4558

    ID: 3090 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTT 2016数学数论

QOJ 985_4558

标题: 组合数问题 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

组合数 Cnm 表示的是从 n 个物品中选出 m 个物品的方案数。举个例子,从 (1,2,3) 三个物品中选择两个物品可以有 (1,2),(1,3),(2,3) 这三种选择方法。根据组合数的定义,我们可以给出计算组合数 Cnm 的一般公式:

Cnm=n!m!(n−m)!

其中 n!=1×2×⋯×n。(额外的,当 n=0 时, n!=1)

小葱想知道如果给定 n,m 和 k,对于所有的 0≤i≤n,0≤j≤min(i,m) 有多少对 (i,j) 满足 Cij 是 k 的倍数。

答案对 109+7 取模。

输入格式

第一行有两个整数 t,k,其中 t 代表该测试点总共有多少组测试数据。

接下来 t 行每行两个整数 n,m。

输出格式

t 行,每行一个整数代表所有的 0≤i≤n,0≤j≤min(i,m) 中有多少对 (i,j) 满足 Cij 是 k 的倍数。

样例一

input

1 2
3 3

output

1

explanation

在所有可能的情况中,只有 C21=2 是 2 的倍数。

样例二

input

2 5
4 5
6 7

output

0
7

样例三

input

3 23
23333333 23333333
233333333 233333333
2333333333 2333333333

output

851883128
959557926
680723120

限制与约定

对于 20% 的测试点,1≤n,m≤100;

对于另外 15% 的测试点,n≤m;

对于另外 15% 的测试点, k=2;

对于另外 15% 的测试点, m≤10;

对于 100% 的测试点, 1≤n,m≤1018,1≤t,k≤100,且 k 是一个质数。