题目描述

Watson 和 Sherlock 是健身伙伴。

他们的健身教练给了他们三个数 $A$、$B$ 和 $N$，并要求 Watson 和 Sherlock 选出两个不同的正整数 $i$ 和 $j$，且 $i$ 和 $j$ 均不超过 $N$。Watson 每天需要恰好吃 $i^A$ 个豆芽，Sherlock 每天需要恰好吃 $j^B$ 个豆芽。

Watson 和 Sherlock 注意到，如果某一天他们两人吃的豆芽总数能被某个整数 $K$ 整除，那么他们在那一天就会相处融洽。

因此，Watson 和 Sherlock 需要你帮忙计算有多少对 $(i, j)$ 满足 $i \neq j$。由于对数可能非常大，请输出答案对 $10^9+7$（即 $1000000007$）取模的结果。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例由一行四个整数 $A$、$B$、$N$ 和 $K$ 组成，含义如上所述。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是所需的答案。

3
1 1 5 3
1 2 4 5
1 1 2 2

Case #1: 8
Case #2: 3
Case #3: 0

提示

在样例 $1$ 中，可能的对为 $(1, 2)$、$(1, 5)$、$(2, 1)$、$(2, 4)$、$(4, 2)$、$(4, 5)$、$(5, 1)$ 和 $(5, 4)$。

在样例 $2$ 中，可能的对为 $(1, 2)$、$(1, 3)$ 和 $(4, 1)$。

在样例 $3$ 中，由于 $i \neq j$，没有可能的对。

限制条件

$1 \le T \le 100$。

$0 \le A \le 10^6$。

$0 \le B \le 10^6$。

小数据集（测试集 1 – 可见）

$1 \le K \le 10000$。

$1 \le N \le 1000$。

大数据集（测试集 2 – 隐藏）

$1 \le K \le 100000$。

$1 \le N \le 10^{18}$。

翻译由 DeepSeek V4 Pro 完成