← 返回题目列表

AtCoder · code_festival_2017_qualc_e

E. 立方体

中文机器翻译题面 查看原题

分数: 1600 点

问题陈述

我们构造了一个长方体的尺寸 A \times B \times C 建成 ABC 侧面立方块 1。 然后,我们将平行六面体放入 xyz- 空格如下:

  • 对于每个三元组 i, j, k (0 \leq i < A, 0 \leq j < B, 0 \leq k < C),存在一个具有连接点的对角线的块 (i, j, k) 和 (i + 1, j + 1, k + 1)。块的所有边都平行于坐标轴。

对于每个三元组 i, j, k,我们将上面的块称为块 (i, j, k).

对于两个块 (i_1, j_1, k_1) 和 (i_2, j_2, k_2),我们将它们之间的距离定义为 max(|i_1 - i_2|, |j_1 - j_2|, |k_1 - k_2|).

我们将一根厚度可以忽略不计的电线穿过连接点的线段 (0, 0, 0) 和 (A, B, C)。 有多少块 (x,y,z) 满足以下条件?求计数模数 10^9 + 7.

  • 存在一个块 (x', y', z') 使电线穿过块内部 (x', y', z') (不仅仅是边界)和块之间的距离 (x, y, z) 和 (x', y', z') 最多是 D.

约束

  • 1 \leq A < B < C \leq 10^{9}
  • 三个整数中的任意两个 A, B 和 C 互质。
  • 0 \leq D \leq 50,000

输入

输入由标准输入按以下格式给出:

A B C D

输出

打印满足条件的块的数量,模 10^9 + 7.


示例输入 1

3 4 5 1

示例输出 1

54

下图显示了平行六面体,被平行于 xy- 平面。 这里,区域中的层 i - 1 \leq z \leq i 称为图层 i.

漆成黑色的方块被电线穿透,并且满足条件。 满足条件的其他块被涂成黄色。

b09f2a541e463456c01d148eabdf36c3.png

有 54 被涂成黑色或黄色的方块。


示例输入 2

1 2 3 0

示例输出 2

4

有四个块被电线穿透,只有这些块满足条件。


示例输入 3

3 5 7 100

示例输出 3

105

所有块都满足条件。


示例输入 4

3 123456781 1000000000 100

示例输出 4

444124403

示例输入 5

1234 12345 1234567 5

示例输出 5

150673016

示例输入 6

999999997 999999999 1000000000 50000

示例输出 6

8402143