SP11276 ADVNTURE - Adventure

Rand 长时间呆在坐标 (0,0,0) 的飞船内，有一天他感到无趣，决定去进行一次冒险。 为了开始冒险，Rand 首先需要选择一个与原点不同的目标点 (x,y,z)，且满足 0≤x≤A，0≤y≤B，0≤z≤C。为了到达这个目标点，Rand 将沿直线从原点出发。在路线中，他可能会遇到一些其他的整数坐标点（格点）。从一个格点到下一个格点的每一段旅程被称为一个阶段。（例如，如果目标点是 (1,2,3)，只有一个阶段，即从 (0,0,0) 到 (1,2,3)；如果目标点是 (3,0,3)，则有三个阶段：从 (0,0,0) 到 (1,0,1)，从 (1,0,1) 到 (2,0,2)，再到 (3,0,3)）。 在每个阶段，Rand 有 K 种不同的活动可以选择来打发时间。你需要计算所有可能的不同冒险方案的总数，结果需要对 1000000007 (1e9+7) 取模。当目标点不同或某阶段选择的活动不同，这两个冒险被认为是不同的。

第一行输入一个整数 T，表示测试用例的数量。 接下来的 T 行中，每行包含四个整数 A、B、C 和 K，分别对应一个测试用例。

针对每一个测试用例，输出一个整数，表示不同冒险方案的总数。

- 1 ≤ T ≤ 100,000 - 1 ≤ A, B, C ≤ 1,000,000 - 1 ≤ K ≤ 1,000,000 **本翻译由 AI 自动生成**