Counting Triangles Containing the Center

An alien UFO has crashed on Earth. The alien captain survived, but his watch did not escape the mishap. The watch is similar to a human watch: it has a 30 mm diameter dial with three hands of lengths \(A, B, C\) (in micrometers, where \(1000 \le A, B, C \le 15000\)). However, time is measured differently by the aliens: one minute consists of \(N\) (\(2 \le N < 2^{32}\)) seconds. Therefore, there are \(N\) tick marks around the dial instead of the usual 60.

The glass has shattered and the three hands have become loose; each can independently rotate to point at any tick mark. When the tips of the three hands (provided they are not collinear) are connected, they form a triangle.

The alien captain ponders the following question: Among all such triangles that can be formed by assigning each hand an arbitrary tick mark such that the three corresponding points are non‐collinear, how many triangles contain the center of the dial? (A triangle is counted even if the center lies exactly on one of its sides.)

Hint: When the three tip points lie on the circumference of a circle, the triangle contains the center if and only if the points are not all contained in any semicircle. In this problem the hands are fixed at distances \(A, B, C\) from the center (with \(A, B, C > 0\)) and hence the condition for including the center depends only on the angles. It turns out that the count is given by the formula:

[ M = \binom{N}{3} - N \cdot \binom{\lfloor (N-1)/2 \rfloor}{2} ]

Note that if \(N < 3\) no triangle can be formed, so the answer in that case is 0.

inputFormat

The input consists of four space‐separated integers:

• \(A\): the length of the first hand (in micrometers).
• \(B\): the length of the second hand (in micrometers).
• \(C\): the length of the third hand (in micrometers).
• \(N\): the number of tick marks on the dial.

outputFormat

Output a single integer \(M\), the number of triangles (formed by choosing one tick for each hand, provided the three points are non-collinear) that contain the center of the dial.

sample

1000 1000 1000 3

1