组合数问题 ### 题目描述 组合数表示的是从 $n$ 个物品中选出 $m$ 个物品的方案数。举个例子，从（1，2，3） 三个物品中选择两个物品可以有 （1，2），（2，3），（1，3）这三种选择方法。 根据组合数的定义，我们可以给出计算组合数的一般公式： $C_{n}^{m}=\frac{n!}{m!(n-m)!}$ 其中 $n! = 1 \times 2 \times \cdots \times n$。 小葱想知道如果给定 $n，m, k$，对于所有的 $0 \leq i \leq n，0 \leq j \leq \min(i,m)$ 有多少对(i,j)满足 $C_{i}^{j}$ 是 k 的倍数。 ### 输入描述 第一行有两个整数 $t，k$，其中 $t$ 代表该测试点总共有多少组测试数据，$k$ 的意义见题干。 接下来 行每行两个整数 $n，m$，其中 $n，m$ 的意义见题干。 其中，$3 \leq n,m \leq 2000，2 \leq k \leq 21，1 \leq t \leq 10^4$。 ### 输出描述 输出 $t$ 行，每行一个整数代表所有的 $0 \leq i \leq n，0 \leq j \leq \min(i,m)$ 有多少对 $(i,j)$ 满足 $C_{i}^{j}$ 是 $k$ 的倍数。 ### 输入输出样例 #### 示例 1 > 输入 ```txt 1 2 3 3 ``` > 输出 ```txt 1 ``` #### 示例 2 > 输入 ```txt 2 5 4 5 6 7 ``` > 输出 ```txt 0 7 ```