ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

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

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Дана система линейных антиуравнений по модулю 3:
a11 · x1 + a12 · x2 + … + a1n · xnb1 mod 3
a21 · x1 + a22 · x2 + … + a2n · xnb2 mod 3

ak1 · x1 + ak2 · x2 + … + akn · xnbk mod 3
Вычислите количество различных целочисленных решений этой системы, для которых 0 ≤ xi ≤ 2.

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

В первой строке записаны целые числа k и n — количество антиуравнений и количество неизвестных (1 ≤ k, n ≤ 30). В i-й из следующих k строк записаны целые числа ai1, ai2, …, ain, bi (0 ≤ aij, bi ≤ 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.