Description

A cube is partitioned into $n\times n\times n$ unit cubes, with coordinates denoted by $(X, Y, Z)$ where $1\le X, Y, Z\le n$. Each unit cube contains an integer whose absolute value does not exceed $10^9$. Count how many subcubes have the sum of all numbers being a multiple of $m$. A subcube is the set of all unit cubes satisfying $x_1\le X\le x_2$, $y_1\le Y\le y_2$, $z_1\le Z\le z_2$, where $1\le x_1, x_2, y_1, y_2, z_1, z_2\le n$.

Input Format

The first line contains two integers $n, m$, representing the edge length of the cube and the positive integer divisor.

The following $n\times n$ lines each contain $n$ integers. First come the $n$ unit cubes with $X=1, Y=1$ (i.e., $Z=1,2,\dots,n$), then $X=1, Y=2$, …, and finally $X=n, Y=n-1$ and $X=n, Y=n$, for a total of $n^3$ integers.

Output Format

Output a single number: the number of subcubes whose sum of integers is a multiple of $m$.

2 5
1 2
3 4
5 6
7 8

5

Hint

Constraints and Conventions

• $30\%$ of the testdata satisfies $1\le n\le 10$.
• $100\%$ of the testdata satisfies $1\le n\le 40$.

For all testdata, $1\le m\le 10^6$.

Translated by ChatGPT 5