P5864 [SEERC 2018] Broken Watch

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.)

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

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

Translated by ChatGPT 5