C0133 [2016提高组Day2-A]组合数问题

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

$C^m_n=\frac{n!}{m!(n-m)!}$

其中 $n!=1 \times 2 \times ... \times n$。

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

样例输入 1

1 2
3 3

样例输出 1

1

样例输入 2

2 5
4 5
6 7

样例输出 2

0
7