1810. Antiequations @ Timus Online Judge

1810. Antiequations

Time limit: 1.0 second
Memory limit: 64 MB

There is a system of linear antiequations modulo 3:

a₁₁ · x₁ + a₁₂ · x₂ + … + a_1n · x_n ≠ b₁ mod 3
a₂₁ · x₁ + a₂₂ · x₂ + … + a_2n · x_n ≠ b₂ mod 3
…
a_k1 · x₁ + a_k2 · x₂ + … + a_kn · x_n ≠ b_k mod 3

Find the number of different solutions of this system assuming that x_i are integers and 0 ≤ x_i ≤ 2.

Input

First line contains two integers: the amount of antiequations k and the amount of variables n (1 ≤ k, n ≤ 30). The i-th of the following k lines contains integers a_i1, a_i2, …, a_in, b_i (0 ≤ a_ij, b_i ≤ 2).

Output

Output the number of solutions of the system.

Samples

input	output
3 3 2 2 1 1 2 1 0 0 1 2 2 2	8
4 3 2 2 1 1 2 1 0 0 1 2 2 2 1 0 1 2	6

Problem Source: Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010.