Description

A UFO crashed on Earth. The alien captain survived, but his watch did not.

The alien watch is very similar to a human watch: it has a dial with a diameter of $\text{30 mm}$, and three hands with lengths $A$, $B$, and $C$ $(1000 \leq A, B, C \leq 15000)$ micrometers. However, aliens use different time units: one minute has $N$ seconds $(2 \leq N < 2^{32})$. Therefore, there are $N$ tick marks on the rim of the dial instead of $60$.

The glass panel of the watch is broken, and the hands are loose: they can rotate freely and independently. Let the three hands point to any tick marks. Then the tips of the three hands can form a triangle (assuming the three hands are not collinear).

Before rescue arrives, the alien has nothing to do and thinks about the following problem: among all triangles formed in the way described above, how many triangles contain the center of the dial (denote the answer by $M$)? (Triangles where the center lies on one side of the triangle should also be counted.)

Input Format

A single line contains integers $A$, $B$, $C$, and $N$, separated by one space.

Output Format

Output the value of $M \bmod 2^{64}$.

15000 15000 15000 2

0

5000 10000 15000 3

6

15000 15000 15000 3

1

15000 15000 15000 4

4

15000 15000 15000 5

5

15000 15000 15000 6

14

Hint

Translated by ChatGPT 5