Counting Subcuboids Divisible by m

You are given a cube of size \(n\times n\times n\) which is subdivided into unit cubes. Each unit cube, identified by coordinates \((X,Y,Z)\) with \(1 \le X,Y,Z \le n\), contains an integer whose absolute value does not exceed \(10^9\). A subcuboid is defined by choosing two coordinates in each dimension: \(x_1 \le X \le x_2\), \(y_1 \le Y \le y_2\), and \(z_1 \le Z \le z_2\) where \(1 \le x_1 \le x_2 \le n\) (and similarly for \(y\) and \(z\)).

Your task is to count how many subcuboids have a sum of all contained numbers that is divisible by a given integer \(m\). That is, if \(S\) is the sum of numbers in a subcuboid, you need to count it if \(S\) is a multiple of \(m\) (i.e. \(S \equiv 0 \; (\mathrm{mod}\; m)\)).

The sum in any subcuboid defined by indices \((x_1,y_1,z_1)\) to \((x_2,y_2,z_2)\) can be computed using a 3D prefix sum. In particular, if we denote \(P(i,j,k)\) as the sum of all values in the subcube from \((1,1,1)\) to \((i,j,k)\), then the sum of the subcuboid is given by:

[ S = P(x_2,y_2,z_2) - P(x_1-1,y_2,z_2) - P(x_2,y_1-1,z_2) - P(x_2,y_2,z_1-1) ] [

• P(x_1-1,y_1-1,z_2) + P(x_1-1,y_2,z_1-1) + P(x_2,y_1-1,z_1-1) - P(x_1-1,y_1-1,z_1-1). ]

Count and output the number of subcuboids for which \(S \equiv 0 \; (\mathrm{mod}\; m)\).

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) (where \(n\) is the side length of the cube and \(m\) is the modulus). Following that are \(n^3\) integers, which represent the numbers in the cube. The numbers are given in order with the innermost loop being the \(Z\)-coordinate, then \(Y\), and then \(X\). In other words, the order is: for \(X = 1\) to \(n\), for \(Y = 1\) to \(n\), for \(Z = 1\) to \(n\).

outputFormat

Output a single integer: the number of subcuboids whose sum is divisible by \(m\).

sample

1 3
6

1