题目描述

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

问题一：给定 $n$ 个在 $\mathrm{GF}(3)$ 上的 $m$ 维向量，记它们张成的线性空间为 $V$。求从 $n$ 个向量中选出一组向量，使得它们是 $V$ 的基的方案数。对 $3$ 取模。

问题二：给定 $n$ 个在 $\mathrm{GF}(2)$ 上的 $m$ 维向量，记它们张成的线性空间为 $V$。其中第 $i$ 个向量有颜色 $c_i$。求从每种颜色中恰好选出一个向量，使得它们是 $V$ 的基的方案数。对 $2$ 取模。

注：为了凸显主要矛盾而忽略次要矛盾，保证 $V$ 的维数为 $m$。

输入格式

第一行包含一个正整数 $\mathrm{taskid}$，表示需要解决的问题编号。

第二行包含两个正整数 $n, m$，含义见上。

接下来输入 $n$ 行：

如果 $\mathrm{taskid} = 1$，则第 $i$ 行包含 $m$ 个非负整数 $v_{i,1}, v_{i,2}, \dots, v_{i,m}$，描述了第 $i$ 个向量。

如果 $\mathrm{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\%$ 的数据，$\mathrm{taskid} \in \{1, 2\}$，$1 \leq n, m \leq 500$。

当 $\mathrm{taskid} = 1$ 时，则 $v_{i,j} \in \{0,1,2\}$。

当 $\mathrm{taskid} = 2$ 时，则 $v_{i,j} \in \{0, 1\}$，$c_i \in [1, m]$。

$\mathrm{subtask}\,1\ (50\,\mathrm{pts})$：$\mathrm{taskid} = 1$。

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