Вам необходимо решить две независимые (но похожие) подзадачи:
Задача 1: Даны $n$ векторов размерности $m$ над полем $\mathrm{GF}(3)$. Пусть $V$ — линейное пространство, натянутое на эти векторы. Найдите количество способов выбрать подмножество из данных $n$ векторов так, чтобы они образовывали базис пространства $V$. Ответ выведите по модулю $3$.
Задача 2: Даны $n$ векторов размерности $m$ над полем $\mathrm{GF}(2)$. Пусть $V$ — линейное пространство, натянутое на эти векторы. У каждого вектора $i$ есть цвет $c_i$. Найдите количество способов выбрать ровно по одному вектору каждого цвета так, чтобы выбранные векторы образовывали базис пространства $V$. Ответ выведите по модулю $2$.
Примечание: Чтобы сосредоточиться на основной сути задачи, гарантируется, что размерность пространства $V$ равна $m$.
Входные данные
Первая строка содержит целое число $taskid$, обозначающее номер решаемой задачи.
Вторая строка содержит два целых числа $n$ и $m$, значения которых описаны выше.
Далее следуют $n$ строк:
Если $taskid = 1$, то $i$-я строка содержит $m$ целых неотрицательных чисел $v_{i,1},v_{i,2},\dots,v_{i,m}$, описывающих $i$-й вектор.
Если $taskid = 2$, то $i$-я строка содержит $m + 1$ целое неотрицательное число $v_{i,1},v_{i,2},\dots,v_{i,m},c_i$, описывающих $i$-й вектор и его цвет.
Выходные данные
Выведите одно целое число — ответ на задачу.
Примеры
Пример 1
Входные данные
1 3 2 0 1 1 2 1 1
Выходные данные
0
Пример 2
Входные данные
1 4 3 1 1 0 1 2 0 1 2 2 1 1 1
Выходные данные
1
Пример 3
Входные данные
1 5 3 1 1 0 0 1 2 0 2 0 2 0 2 2 2 2
Выходные данные
2
Пример 4
Входные данные
2 3 2 0 1 1 0 0 2 1 1 1
Выходные данные
0
Пример 5
Входные данные
2 4 2 1 1 1 0 0 1 1 0 2 0 0 2
Выходные данные
1
Подзадачи
Для $100\%$ данных: $taskid\in \{1, 2\}, 1 \leq n, m \leq 500$.
Если $taskid = 1$, то $v_{i,j}\in \{0,1,2\}$.
Если $taskid = 2$, то $v_{i,j}\in\{0, 1\}, c_i\in[1, m]$.
$\mathrm{subtask}\,1(50\,\mathrm{баллов}) : taskid = 1$.
$\mathrm{subtask}\,2(50\,\mathrm{баллов}) : taskid = 2$.