color

Zăhărel are un set de $N$ becuri colorate cu $K$ culori (pentru uşurinţă vom considera culorile numerotate de la $1$ la $K$). Fiecare bec este special, în sensul că are un comutator care îi schimbă culoarea $c$ curentă astfel:

• dacă $c = K$, culoarea devine $1$
• dacă $c < K$, culoarea devine $c+1$

Zăhărel doreşte să comute anumite becuri astfel încât toate să aibă aceeaşi culoare $C$. Totusi, sarcina lui nu este atât de simplă, deoarece nu poate comuta becurile direct, ci trebuie să folosească o telecomandă cu $M$ butoane. Apăsarea unui buton afectează fiecare bec, mai exact, pentru fiecare buton $i$ se dau $N$ valori $A_{i,1} \ A_{i,2} \dots A_{i,N}$ cu semnificaţia că becul $j$ este comutat de $A_{i,j}$ ori când se apasă butonul $i$.

Cerință

Scrieţi un program care determină în câte moduri poate folosi Zăhărel cele $M$ butoane astfel încât toate becurile să aibă culoarea $C$.

Date de intrare

Fişierul de intrare color.in conţine pe prima linie numerele naturale $N \ M \ K \ C$ separate prin spaţii. Următoarea linie va conţine $N$ numere naturale separate prin spaţii reprezentând culorile iniţiale ale becurilor, în ordine de la $1$ la $N$. Următoarele $M$ linii vor conţine câte $N$ numere naturale $A_{i,1} \ A_{i,2} \dots A_{i,N}$, separate prin spaţii, descriind butonul $i$.

Date de ieșire

În fişierul de ieşire color.out se va scrie pe prima linie numărul de moduri de a folosi telecomanda, astfel încât toate becurile să aibă culoarea $C$. Rezultatul se va afişa modulo $666 \ 013$.

Restricții și precizări

• La corectare se vor folosi $10$ teste. Ele vor avea următoarele valori pentru $N$, $M$ si $K$:

• $1 \leq C \leq K$
• $0 \leq A_{i,j} \leq 10^9$
• Un buton de pe telecomandă poate fi apăsat de un număr de ori mai mic decât $K$

Exemplu

color.in

4 6 2 1
1 2 1 2
1 0 1 0
0 1 0 1
1 0 0 0 
0 1 0 0 
0 0 1 0
0 0 0 1

color.out

4

Explicație

Cele $4$ posibilităţi sunt:

1. butonul $2$
2. butoanele $4, 6$
3. butoanele $1, 2, 3, 5$
4. butoanele $1, 3, 4, 5, 6$