一架不明飞行物坠毁在地球上。外星船长在坠机中幸免于难，但他那块可靠的手表却损坏得无法修复。

这块外星手表与人类的手表非常相似：它是一个直径为 $30mm$ 的圆盘，有三根长度分别为 $A, B, C$ 微米的指针（$1000 \le A, B, C \le 15000$）。然而，外星人测量时间的方式不同：他们的一分钟有 $N$ 个外星秒（$2 \le N < 2^{32}$）。因此，圆盘边缘上有 $N$ 个刻度，而不是 60 个。

手表的玻璃盖碎了，指针也松动了：它们可以自由且独立地旋转。通过将每根指针指向任意刻度，它们的尖端可以构成一个假想的三角形（只要它们不共线）。

在等待救援的过程中，外星人思考了这样一个问题：包含手表中心的不同三角形的数量 $M$ 是多少？（三角形的边经过中心的情况也算在内。）

输入格式

输入包含一行，由空格分隔的 $A, B, C$ 和 $N$。

输出格式

输出 $M$ 对 $2^{64}$ 取模的结果。

样例

样例输入 1

15000 15000 15000 2

样例输出 1

0

样例输入 2

5000 10000 15000 3

样例输出 2

6

样例输入 3

15000 15000 15000 3

样例输出 3

1

样例输入 4

15000 15000 15000 4

样例输出 4

4

样例输入 5

15000 15000 15000 5

样例输出 5

5

样例输入 6

15000 15000 15000 6

样例输出 6

14