P16581 [GKS 2016 #B] Sherlock and Watson Gym Secrets

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$ 是所需的答案。

在样例 $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 完成