Counting CCM Pyramid Reconstructions

Archaeologists have recently discovered a mysterious ancient CCM civilization. Their central remnant is a huge stone pyramid built entirely from identical 1×1×1 cubes. Analysis of the pyramid relic revealed the following properties:

• The pyramid is built from several layers. In each layer, the cubes form a connected block when viewed from above.
• Every cube in an upper layer is directly supported by a cube in the layer immediately below it.
• Each layer is strictly symmetric with respect to both the vertical and horizontal axes. Moreover, the symmetry axes of all layers coincide. In addition, when moving from the symmetry axis toward either end, the number of consecutive filled cells in that row (or column) is non‐increasing (i.e. it does not increase).
• Each layer is contained in a square with an even side length. In fact, the maximum length and maximum width of the filled region in each layer are equal and even, since the CCM people believed that even numbers bring luck.
• The pyramid is known to have used a total of $N$ cubes and has a height of $H$ layers. In each layer, archaeologists have estimated the square’s side length $L$, which is even.

For the purpose of reconstruction, suppose that the pyramid is built in a simplified way. In each layer the structure is a centered square block determined by a parameter m (with 1 ≤ m ≤ L/2) such that the filled region is a square of side length $2m$. (Note that $2m$ is even.) Thus the number of cubes in that layer is:

$$\text{cubes} = (2m)^2 = 4m^2.$$

The support condition forces the pyramid layers to form a non‐increasing sequence: if the bottom layer is assigned the parameter m₁, the next layer must choose a parameter m₂ satisfying m₂ ≤ m₁, and so on. In other words, a valid pyramid is determined by a sequence

$$m_1, m_2, \ldots, m_H \quad\text{with}\quad 1 \le m_i \le L/2 \quad\text{and}\quad m_1 \ge m_2 \ge \cdots \ge m_H. $$

The total number of cubes used is then

$$\sum_{i=1}^{H} 4m_i^2 = N.$$

Let $$S=\frac{N}{4}.$$ The problem is to count the number of non‐increasing sequences \(m_1, m_2,\dots, m_H\) with \(1 \le m_i \le L/2\) such that

$$\sum_{i=1}^{H} m_i^2 = S.$$

You are given three integers: N (total number of cubes), H (height of the pyramid) and L (the side length of the square in each layer, an even integer). Output the number of valid pyramids that satisfy the above conditions.

inputFormat

The input consists of a single line containing three integers separated by spaces:
• N — the total number of cubes used in the pyramid;
• H — the number of layers (height of the pyramid);
• L — the side length of the square bounding each layer (an even integer).

Note: It is guaranteed that N is a multiple of 4.

outputFormat

Output a single integer: the number of valid pyramid reconstructions.

sample

4 1 2

1