题目描述

倒霉的科学家 Vasya 受够了同事们没完没了的嘲笑，于是造了一台时间机器，准备前往未来。然而，机器却把他送到了过去，随后还爆炸了。

为了谋生，Vasya 成为了亚瑟王的宫廷炼金术士。他接到的第一个任务是制造贤者之石。

Vasya 找到了 $K$ 种原料，并不断尝试按不同的比例混合它们。形式化地，一次实验由一个方案

描述，其中 $a_i$ 表示第 $i$ 种原料取用的盎司数。

所有原料会被放入坩埚中，充分混合并加热。每个 $a_i$ 都是非负整数，并且

其中 $S$ 是坩埚的容量。

每次实验至少使用两种原料，也就是说，至少有两个 $a_i$ 严格大于 $0$。

遗憾的是，Vasya 到目前为止做过的所有实验都失败了——每一种混合物都发生了爆炸。国王已经非常不满，并决定只再给他最后一次机会。如果明天的实验仍然爆炸，Vasya 就会被处死。

幸运的是，Vasya 发现了一种排除必然失败方案的方法：

如果某个实验方案

已经发生过爆炸，那么任意满足

的方案

也一定会爆炸。

Vasya 想统计：根据已有实验记录，有多少个可能的实验方案尚不能被确定为一定会爆炸。

输入格式

第一行包含三个整数 $K,S,M$：

• $2\le K\le 30$，表示原料种数；
• $2\le S\le 10000$，表示坩埚容量；
• $0\le M\le 20$，表示 Vasya 已经进行过的实验数。

接下来 $M$ 行，每行包含 $K$ 个整数，描述一个已经发生过爆炸的实验方案。

题目保证这些记录均为合法实验方案。

输出格式

输出一个整数，表示尚不能确定一定会爆炸的实验方案数量。

样例输入

2 4 2
1 3
2 1

样例输出

2

数据范围与限制

• $2\le K\le 30$
• $2\le S\le 10000$
• $0\le M\le 20$