您需要解決兩個獨立（但類似）的子問題：

問題一：給定 $n$ 個在 $\mathrm{GF}(3)$ 上的 $m$ 維向量，記它們張成的線性空間為 $V$。求從 $n$ 個向量中選出一組向量，使得它們是 $V$ 的基的方案數。對 $3$ 取模。

問題二：給定 $n$ 個在 $\mathrm{GF}(2)$ 上的 $m$ 維向量，記它們張成的線性空間為 $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

範例 1 輸出

0

範例 2 輸入

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

範例 2 輸出

1

範例 3 輸入

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

範例 3 輸出

2

範例 4 輸入

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

範例 4 輸出

0

範例 5 輸入

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

範例 5 輸出

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{pts}) : taskid = 1$。

$\mathrm{subtask}\,2(50\,\mathrm{pts}) : taskid = 2$。