问题 Y: 配方

问题 Y: 配方

时间限制: 1 Sec  内存限制: 128 MB
提交: 36  解决: 11
[提交] [状态] [讨论版] [命题人:]

题目描述

某种食品由k种原料组成(1≤k≤16),每种原料的编号为1,2,3,…,k。同时有n个人(1≤n≤1000),每个人对食品中的原料有一定的要求。全部的要求是一个n×k的矩阵。
a[1,1] a[1,2] a[1,3] ... a[1,k]
a[2,1] a[2,2] a[2,3] ... a[2,k]
...
a[n,1] a[n,2] a[n,3] ... a[n,k]
a[i,j] =1,表示第i个人对第j种原料要求一定要有。
a[i,j] =2,表示第i个人对第j种原料要求一定不能有。
a[i,j] =0,表示第i个人对第j种原料要求可有可无。
那么,当n,k和要求矩阵给出之后,求出所有符合要求的食品方案数。若不可能,则输出-1。

输入

第一行2个整数n和k,接下来n行,每行k个数据,每个数据分别为0,1或2,表示要求矩阵。

输出

一个整数,表示所有符合要求的食品方案数,如不可能,输出-1。

样例输入

2 3
1 0 1
0 0 1

样例输出

2

[提交][状态]