Description

夹克老爷家里有很多水田，水田里种了好多槐树。其中每块水田可以看作是一个长为\(N\)，宽为\(M\)的矩形，每棵槐树可以看做一个底边边长为\(L\)的正四棱柱(想想Minecraft)。

现在夹克老爷又购得了一块水田。鉴于之前水田里的槐树种的歪歪斜斜的，夹克老爷希望这块新田里的槐树能变得整齐。也就是说，夹克老爷希望新种的每棵槐树的边缘与和其相邻的槐树的边 缘(或相邻的水田边缘)的距离都相等（如图所示）。

夹克老爷希望聪明的你能够告诉他有多少种种法。

Format

Input

输入只有一行，从左到右依次为\(N\),\(M\),\(L\)

Output

输出一行表示答案 如果不存在合法的种法，应当输出\(0\)

Sample 1

Input

2 2 1

Output

2

Limitation

1s, 512MiB for each test case.

Hint

数据范围

有10%的数据，答案不超过\(0\)
另有20%的数据，\(N,M\)均为\(L\)的倍数
另有30%的数据，\(max\{N/L,M/L\}<1000\)
对100%的数据，\(N,M,L\)皆是整数，\(1 \leq N,M,L \leq 1000,000,000,0000\)
答案在64位有符号整数所能表示的范围内

间隔小于\(0\)或种\(0\)棵树不被视作一种合法的种法。
只要一棵槐树的位置能够指定，夹克老爷总能把它种到任意精度的位置。

样例解释

当且仅当间隔为\(0\)和\(0.5\)的时候有\(2\)种种法

Source

CSP 2019 综合测试题（四）