실험 "X": 예정된 폭발

과학자 Vasya는 궁정 연금술사가 되었고, 재료들을 섞어 현자의 돌을 만들어야 합니다.

재료는 모두 $K$가지입니다. 하나의 실험은 계획 $(a_1, a_2, \dots, a_K)$로 나타냅니다. Vasya는 $i$번째 재료를 $a_i$온스만큼 덜어 도가니에 모두 넣고 가열합니다. 각 $a_i$는 음이 아닌 정수이고, 전체 양은 도가니 용량 $S$를 넘을 수 없으므로 $a_1 + a_2 + \dots + a_K \le S$입니다. 또한 모든 실험에서는 최소 두 종류의 재료를 실제로 사용합니다. 즉 $a_i$ 중 적어도 두 개는 양수입니다.

지금까지 모든 혼합물이 폭발했습니다. Vasya는 단조성 규칙을 발견했습니다. 어떤 계획 $(a_1, \dots, a_K)$가 폭발한다면, 모든 $i$에 대해 $b_i \ge a_i$인 계획 $(b_1, \dots, b_K)$도 반드시 폭발합니다.

Vasya는 이미 $M$번의 실험을 했고, 그 모두가 폭발했습니다. 어떤 계획이 이 규칙에 의해 반드시 폭발한다고 확정되면 그 계획을 확실히 실패라고 부릅니다. 즉, 폭발했던 $M$개의 계획 $(c_1, \dots, c_K)$ 중 하나라도 모든 $i$에 대해 $a_i \ge c_i$를 만족하면 그 계획은 확실히 실패입니다.

유효한 실험 계획 중 확실히 실패가 아닌 것이 몇 개인지 세십시오. 계획이 유효하다는 것은 모든 $a_i$가 음이 아닌 정수이고, $a_1 + \dots + a_K \le S$이며, $a_i$ 중 적어도 두 개가 양수임을 뜻합니다.

첫 번째 줄에 세 정수 $K$, $S$, $M$이 주어집니다 ($2 \le K \le 30$, $2 \le S \le 10000$, $0 \le M \le 20$). 여기서 $M$은 이미 진행한 실험의 수입니다. 이어지는 $M$개의 줄에는 각각 $K$개의 정수가 주어지며, 이미 진행한(모두 폭발한) 실험 하나를 나타냅니다.

확실히 실패가 아닌 유효한 실험 계획의 개수를 정수 하나로 출력하십시오. 이 값은 매우 클 수 있으므로 정확한 값을 그대로 출력하십시오.