该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

它不是一切。幸福的活着比较重要。比如多睡觉。

虽然它很不可解，但是这道题很可解，我不好说你会不会觉得它好玩但是我觉得挺好玩的。

题目描述

给定一个正整数 $n$，找出每一个 $k$ 进制下的没有前导零的正整数 $x$ 使得 $x$ 的每一位的和等于 $n$，记所有这样的 $x$ 组成一个集合 $S$。

对于 $S$ 中的每一个数 $x$，求出它每一位的乘积为 $f(x)$，令所有的 $f(x)$ 组成一个集合 $T$。求集合 $T$ 的大小，答案对 $10^9+7$ 取模。

输入格式

本题包含多组测试数据。第一行一个正整数 $t$ 表示测试数据的数量。

接下来 $t$ 行，每行两个正整数 $n, k$。

输出格式

对于每组数据，输出一行一个整数表示答案。

样例

样例输入 1

3
1 2
2 3
3 4

样例输出 1

2
3
4

样例 1 解释

• 对于第一组数据，$n = 1, k = 2$，$T = \{0, 1\}$，故答案为 $2$。
• 对于第二组数据，$n = 2, k = 3$，$T = \{0, 1, 2\}$，故答案为 $3$。
• 对于第三组数据，$n = 3, k = 4$，$T = \{0, 1, 2, 3\}$，故答案为 $4$。

样例输入/输出 2

见下发文件 myself2.in/ans。该样例满足测试点 $7 \sim 8$ 的限制。

样例输入/输出 3

见下发文件 myself3.in/ans。该样例满足测试点 $18 \sim 20$ 的限制。

数据范围与提示

本题共 $20$ 个测试点，每个测试点 $5$ 分。

对于所有数据，$1 \le n, t \le 10 ^ 6$，$2 \le k \le 10 ^ 3$。