あなたは2つの独立した（しかし類似した）サブ問題を解決する必要があります。

問題1：$\mathrm{GF}(3)$ 上の $m$ 次元ベクトルが $n$ 個与えられます。それらが張る線形空間を $V$ とします。$n$ 個のベクトルから $V$ の基となるようなベクトルの組を選ぶ方法の数を求めてください。結果は $3$ を法として出力してください。

問題2：$\mathrm{GF}(2)$ 上の $m$ 次元ベクトルが $n$ 個与えられます。それらが張る線形空間を $V$ とします。各 $i$ 番目のベクトルには色 $c_i$ が割り当てられています。各色からちょうど1つずつベクトルを選び、それらが $V$ の基となるような方法の数を求めてください。結果は $2$ を法として出力してください。

注：主要な論点に集中するため、$V$ の次元は $m$ であることが保証されています。

入力

1行目に、解決すべき問題番号を表す正整数 $taskid$ が与えられます。

2行目に、2つの正整数 $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

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

小課題

すべてのデータにおいて、$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$。