题目描述

一架 UFO 坠毁在地球上。外星人船长幸免于难，但他的手表没能逃过这一劫。

外星人的手表和人类的手表非常相似：手表有一个直径为 $\text{30 mm}$ 的表盘，有三个表针，长度分别为 $A, B$ 和 $C \ (1000 \leq A, B, C \leq 15000)$ 微米。然而，外星人有不同的时间单位：$1$ 分钟里有 $N \ (2 \leq N < 2^{32})$ 秒。因此，表盘的边缘上有 $N$ 个刻度而不是 $60$ 个。

手表的玻璃面板已经摔碎，表针也松了：它们可以独立地自由旋转。让三个表针分别指向任意刻度，以表针的尖端的顶点可以构成一个三角形（表针不共线的前提下）。

在救援来之前外星人闲着没事干，就思考起了这样一个问题：按上述方法构成的三角形中，有多少个三角形包含了表盘的中心（答案记为 $M$）。（表盘中心在三角形的某一边上的三角形也要统计。）

输入格式

仅一行包含整数 $A, B, C$ 和 $N$，四个数字之间用一个半角空格隔开。

输出格式

输出 $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