题目描述

某种食品由 $k$ 种原料组成 $(1 \le k \le 16)$，每种原料的编号为 $1$ 、 $2$ 、 $3, \dots, k$。同时有 $n$ 个人 $(1 \le n \le 1000)$，每个人对食品中的原料有一定的要求。全部的要求是一个 $n \times k$ 的矩阵。

$a_{11}\ a_{12}\ a_{13}\ \dots\ a_{1k}$
$a_{21}\ a_{22}\ a_{23}\ \dots\ a_{2k}$
$\dots \quad \dots \quad \dots \quad \dots \quad \dots$
$a_{n1}\ a_{n2}\ a_{n3}\ \dots\ a_{nk}$

其中：
$a_{ij}=1$，表示第 $i$ 人对第 $j$ 种原料要求一定要有。
$a_{ij}=2$，表示第 $i$ 人对第 $j$ 种原料要求一定不能有。
$a_{ij}=0$，表示第 $i$ 人对第 $j$ 种原料要求可有可无。

那么，当 $n$ 、 $k$ 和要求矩阵给出之后，求出所有符合要求的食品方案数。若不可能，则输出 $-1$。

例如， $n=2$， $k=3$，要求矩阵为：

1 0 1
0 0 1

则符合要求的食品方案数有 $2$ 种，即食品的三种原料为有、有、有或有、无、有均可，故有 $2$ 种方案。

输入格式

第一行输入两个整数 $n$ 和 $k$，用空格隔开，接下来输入一个 $n$ 行 $k$ 列的要求矩阵。

输出格式

输出所有符合要求的食品方案数。若不可能，则输出 $-1$。

2 3
1 0 1
0 0 1

2