题目描述

您需要解决两个独立（但类似）的子问题：

问题一：给定 $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

0

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

1

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

2

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

0

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

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