1810. Антиуравнения @ Timus Online Judge

1810. Антиуравнения

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Дана система линейных антиуравнений по модулю 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

Вычислите количество различных целочисленных решений этой системы, для которых 0 ≤ x_i ≤ 2.

Исходные данные

В первой строке записаны целые числа k и n — количество антиуравнений и количество неизвестных (1 ≤ k, n ≤ 30). В i-й из следующих k строк записаны целые числа a_i1, a_i2, …, a_in, b_i (0 ≤ a_ij, b_i ≤ 2).

Результат

Выведите количество решений системы.

Примеры

исходные данные	результат
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

Источник задачи: Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010.