Experiment "X": Explosions Expected

Vasya has taken the post of court alchemist, and his task is to brew the philosopher's stone by mixing ingredients.

There are $K$ ingredients. An experiment is a plan $(a_1, a_2, \dots, a_K)$: Vasya takes $a_i$ ounces of the $i$-th ingredient, pours everything into the crucible, and heats it. Every $a_i$ is a non-negative integer, and the total amount may not exceed the crucible capacity $S$, so $a_1 + a_2 + \dots + a_K \le S$. In every experiment at least two ingredients are actually used: at least two of the $a_i$ are strictly positive.

So far every mixture has exploded. Vasya has spotted a monotonicity rule: if a plan $(a_1, \dots, a_K)$ explodes, then every plan $(b_1, \dots, b_K)$ with $b_i \ge a_i$ for all $i$ explodes as well.

Vasya has already carried out $M$ experiments, and all of them exploded. Call a plan definitely unsuccessful when the monotonicity rule guarantees it will explode, i.e. when at least one of the $M$ exploded plans $(c_1, \dots, c_K)$ satisfies $a_i \ge c_i$ for every $i$.

Count how many valid experiment plans are not definitely unsuccessful. A plan is valid when every $a_i$ is a non-negative integer, $a_1 + \dots + a_K \le S$, and at least two of the $a_i$ are positive.

The first line contains three integers $K$, $S$, and $M$ ($2 \le K \le 30$, $2 \le S \le 10000$, $0 \le M \le 20$), where $M$ is the number of experiments already conducted. Each of the next $M$ lines contains $K$ integers describing one already-conducted experiment (all of which exploded).

Print one integer: the number of valid experiment plans that are not definitely unsuccessful. This count can be very large, so print the exact value.