#552. 【2024-11-23 P2】将不可解的我的一切

【2024-11-23 P2】将不可解的我的一切

题目背景

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

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

题目描述

给定一个正整数 nn,找出每一个 kk 进制下的没有前导零的正整数 xx 使得 xx 的每一位的和等于 nn,记所有这样的 xx 组成一个集合 SS。

对于 SS 中的每一个数 xx,求出它每一位的乘积为 f(x)f(x),令所有的 f(x)f(x) 组成一个集合 TT。求集合 TT 的大小,答案对 109+710^9+7 取模。

输入格式

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

接下来 tt 行,每行两个正整数 n,kn, k。

输出格式

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

样例

样例输入 1

3
1 2
2 3
3 4

样例输出 1

2
3
4

样例 1 解释

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

样例输入/输出 2

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

样例输入/输出 3

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

数据范围与提示

本题共 2020 个测试点,每个测试点 55 分。

测试点编号 特殊性质
11 k=2k = 2
22 k≤3k \le 3,t=1t = 1
3∼43 \sim 4 k≤3k \le 3
5∼65 \sim 6 n≤10n \le 10,t=1t = 1
7∼87 \sim 8 n≤10n \le 10
9∼109 \sim 10 n≤1000n \le 1000,t=1t = 1
11∼1211 \sim 12 n≤1000n \le 1000
13∼1413 \sim 14 k≤10k \le 10,t=1t = 1
1515 k≤10k \le 10
16∼1716 \sim 17 t=1t = 1
18∼2018 \sim 20 无

对于所有数据,1≤n,t≤1061 \le n, t \le 10 ^ 6,2≤k≤1032 \le k \le 10 ^ 3。