Musisz rozwiązać dwa niezależne (lecz podobne) podproblemy:

Problem pierwszy: Dane jest $n$ wektorów $m$-wymiarowych nad ciałem $\mathrm{GF}(3)$. Niech $V$ będzie przestrzenią liniową rozpiętą przez te wektory. Oblicz liczbę sposobów wyboru podzbioru wektorów spośród danych $n$, tak aby tworzyły one bazę przestrzeni $V$. Wynik podaj modulo $3$.

Problem drugi: Dane jest $n$ wektorów $m$-wymiarowych nad ciałem $\mathrm{GF}(2)$. Niech $V$ będzie przestrzenią liniową rozpiętą przez te wektory. Każdy wektor $i$ ma przypisany kolor $c_i$. Oblicz liczbę sposobów wyboru dokładnie jednego wektora z każdego koloru, tak aby wybrane wektory tworzyły bazę przestrzeni $V$. Wynik podaj modulo $2$.

Uwaga: Aby skupić się na głównym aspekcie problemu, gwarantuje się, że wymiar przestrzeni $V$ wynosi $m$.

Wejście

Pierwsza linia zawiera liczbę całkowitą $taskid$, określającą numer rozwiązywanego problemu.

Druga linia zawiera dwie liczby całkowite $n, m$, o znaczeniu jak wyżej.

Następnie podano $n$ linii:

Jeśli $taskid = 1$, to $i$-ta linia zawiera $m$ nieujemnych liczb całkowitych $v_{i,1},v_{i,2},\dots,v_{i,m}$, opisujących $i$-ty wektor.

Jeśli $taskid = 2$, to $i$-ta linia zawiera $m + 1$ nieujemnych liczb całkowitych $v_{i,1},v_{i,2},\dots,v_{i,m},c_i$, opisujących $i$-ty wektor oraz jego kolor.

Wyjście

Wypisz jedną liczbę całkowitą oznaczającą wynik.

Przykład

Przykład 1

1
3 2
0 1
1 2
1 1

Wyjście 1

0

Przykład 2

1
4 3
1 1 0
1 2 0
1 2 2
1 1 1

Wyjście 2

1

Przykład 3

1
5 3
1 1 0
0 1 2
0 2 0
2 0 2
2 2 2

Wyjście 3

2

Przykład 4

2
3 2
0 1 1
0 0 2
1 1 1

Wyjście 4

0

Przykład 5

2
4 2
1 1 1
0 0 1
1 0 2
0 0 2

Wyjście 5

1

Podzadania

Dla $100\%$ danych wejściowych: $taskid\in \{1, 2\}, 1 \leq n, m \leq 500$.

Gdy $taskid = 1$, zachodzi $v_{i,j}\in \{0,1,2\}$.

Gdy $taskid = 2$, zachodzi $v_{i,j}\in\{0, 1\}, c_i\in[1, m]$.

$\mathrm{subtask}\,1(50\,\mathrm{pkt}) : taskid = 1$.

$\mathrm{subtask}\,2(50\,\mathrm{pkt}) : taskid = 2$.