Counting Ordered Triples with XOR Constraint

Given a positive integer \(M\) and \(n\) (with \(n \le 5\)) positive integer triples \((a_i, b_i, c_i)\) such that \(a_i, b_i, c_i \le M \le 2000\), count the number of ordered positive integer triples \((x, y, z)\) with \(1 \le x,y,z \le M\) that satisfy

\[ \forall\, i \; (1 \le i \le n),\quad |a_i - x| \oplus |b_i - y| \oplus |c_i - z| = 9 \]

Here, \(|a_i-x|\) denotes the absolute difference and \(\oplus\) denotes the bitwise XOR operation. Two triples \((x_1, y_1, z_1)\) and \((x_2, y_2, z_2)\) are considered different if at least one coordinate differs.

Note: In C++ the expressions A ^ B ^ C or A xor B xor C compute \(A \oplus B \oplus C\). Use similar bitwise XOR operations in your implementation.

Constraints:
\(1 \le M \le 2000\), \(1 \le a_i, b_i, c_i \le M\) and \(n \le 5\).

Your task is to compute the number of valid \((x,y,z)\) triples.

inputFormat

The first line contains two integers \(M\) and \(n\).
Each of the following \(n\) lines contains three integers \(a_i\), \(b_i\), \(c_i\) separated by spaces.

It is guaranteed that \(1 \le a_i,b_i,c_i \le M \le 2000\) and \(n \le 5\).

outputFormat

Output a single integer: the number of ordered triples \((x, y, z)\) with \(1 \le x,y,z \le M\) satisfying all the conditions.

sample

10 1
1 1 1

40