Cubes

AtCoder

IDcode_festival_2017_qualc_e

Time2000ms

Memory256MB

Difficulty—

We constructed a rectangular parallelepiped of dimensions $A \times B \times C$ built of $ABC$ cubic blocks of side $1$. Then, we placed the parallelepiped in $xyz$\-space as follows: * For every triple $i, j, k$ ($0 \leq i < A, 0 \leq j < B, 0 \leq k < C$), there exists a block that has a diagonal connecting the points $(i, j, k)$ and $(i + 1, j + 1, k + 1)$. All sides of the block are parallel to a coordinate axis. For each triple $i, j, k$, we will call the above block as block $(i, j, k)$. For two blocks $(i_1, j_1, k_1)$ and $(i_2, j_2, k_2)$, we will define the distance between them as max$(|i_1 - i_2|, |j_1 - j_2|, |k_1 - k_2|)$. We have passed a wire with a negligible thickness through a segment connecting the points $(0, 0, 0)$ and $(A, B, C)$. How many blocks $(x,y,z)$ satisfy the following condition? Find the count modulo $10^9 + 7$. * There exists a block $(x', y', z')$ such that the wire passes inside the block $(x', y', z')$ (not just boundary) and the distance between the blocks $(x, y, z)$ and $(x', y', z')$ is at most $D$. ## Constraints * $1 \leq A < B < C \leq 10^{9}$ * Any two of the three integers $A, B$ and $C$ are coprime. * $0 \leq D \leq 50,000$ ## Input Input is given from Standard Input in the following format: $A$ $B$ $C$ $D$ [samples]

Samples

Input #1

3 4 5 1

Output #1

54

The figure below shows the parallelepiped, sliced into five layers by planes parallel to $xy$\-plane. Here, the layer in the region $i - 1 \leq z \leq i$ is called layer $i$.
The blocks painted black are penetrated by the wire, and satisfy the condition. The other blocks that satisfy the condition are painted yellow.

![image](https://img.atcoder.jp/code-festival-2017-qualc/b09f2a541e463456c01d148eabdf36c3.png)

There are $54$ blocks that are painted black or yellow.

Input #2

1 2 3 0

Output #2

4

There are four blocks that are penetrated by the wire, and only these blocks satisfy the condition.

Input #3

3 5 7 100

Output #3

105

All blocks satisfy the condition.

Input #4

3 123456781 1000000000 100

Output #4

444124403

Input #5

1234 12345 1234567 5

Output #5

150673016

Input #6

999999997 999999999 1000000000 50000

Output #6

API Response (JSON)

{
  "problem": {
    "name": "Cubes",
    "description": {
      "content": "We constructed a rectangular parallelepiped of dimensions $A \\times B \\times C$ built of $ABC$ cubic blocks of side $1$. Then, we placed the parallelepiped in $xyz$\\-space as follows: *   For every t",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "code_festival_2017_qualc_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We constructed a rectangular parallelepiped of dimensions $A \\times B \\times C$ built of $ABC$ cubic blocks of side $1$. Then, we placed the parallelepiped in $xyz$\\-space as follows:\n\n*   For every t...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments