Aflându-se la moșia lui Pascalopol, Otilia este fascinată de vasta întindere de pământ pe care bărbatul o deține. Cum Pascalopol este un om darnic și îi face toate poftele Otiliei, încă de când era mică, acesta îi dăruiește tinerei o bucată de pământ de dimensiune N*M împărțită în parcele de dimensiune 1*1, dispuse pe N linii și M coloane (numerotate de la 1 la N, respectiv de la 1 la M). Astfel, fiecare parcelă poate fi identificată prin coordonatele (i,j), unde i reprezintă linia, iar j reprezintă coloana pe care se află parcela.

Bucata de pământ conține și gropi. O parcelă care este groapă este reprezentată prin numărul 1, în timp ce o parcelă care nu este groapă este reprezentată prin numărul 0. Pentru că Felix este gelos pe Pascalopol și nu suportă ca Otilia să-i ofere atât de multă atenție, tânărul i-a pus următoarea întrebare moșierului, vrând prin aceasta să-i arate că el este net superior din punct de vedere informatic:

“- Dacă eu plec din parcela (1,1), iar calul meu poate face un salt cu orice lungime între 1 și K la sud (linia crește) sau la est (coloana crește), în câte moduri pot ajunge în parcela (L,C), ținând cont că nu pot păși pe o parcelă care conține o groapă.”.

Mai formal, dintr-o parcelă de coordonate (i, j), calul se poate deplasa cu un salt în oricare dintre parcelele de coordonate (i+x, j) sau (i, j+x) (1 ≤ x ≤ K) doar dacă parcela este reprezentată prin numărul 0.

Două succesiuni de salturi sunt distincte dacă au număr diferit de salturi sau dacă există o parcelă prin care trece doar una dintre cele două succesiuni.

Pentru că numărul poate fi foarte mare, Felix se mulțumește doar cu restul acestuia la împărțirea cu 1.000.000.007.

Cerința

Cum Pascalopol nu le are cu calculatoarele, iar aceasta este clar o problemă de Informatică, moșierul vă cere ajutorul și vă va oferi în schimb 100 de puncte.

Date de intrare

Fișierul de intrare enigma.in conține pe prima linie numerele naturale N, M, L și C, reprezentând numărul de linii și numărul de coloane ale bucății de pământ, respectiv coordonatele parcelei în care Felix vrea să ajungă. Pe următoarele N linii se vor afla câte M valori 0 sau 1, unde 1 reprezintă o parcelă care este groapă, iar 0 reprezintă o parcelă care nu este groapă. Pe ultima linie se va afla numărul K, reprezentând lungimea maximă a unui salt pe care calul lui Felix îl poate face.

Date de ieșire

Fișierul de ieșire enigma.out va conține o singură linie pe care va fi scris numărul de moduri în care calul poate ajunge din parcela (1,1) în parcela (L,C) prin modalitatea descrisă în enunț, modulo 1.000.000.007.

Restricții și precizări

• 1 ≤ N, M, K ≤ 1000
• Se garantează că Felix vrea să ajungă într-o parcelă care nu este groapă, iar parcela (1,1) nu este groapă.
• Calul nu poate călca pe o parcelă care este groapă, dar poate efectua un salt peste una sau mai multe parcele care sunt gropi.
• Pentru 9 puncte, 1 ≤ N, M, K ≤ 7
• Pentru 11 puncte, 1 ≤ N, M ≤ 1000, iar K = 1
• Pentru 25 de puncte, 1 ≤ N, M, K ≤ 1000 și nu există nicio parcelă groapă
• Pentru 25 de puncte, 8 ≤ N, M, K ≤ 100
• Pentru 30 de puncte, 101 ≤ N, M, K ≤ 1000

Exemplul 1:

enigma.in

5 5 4 3
0 0 1 1 1
1 0 1 0 0
1 0 0 0 0
0 1 0 1 0
0 1 1 1 0
2

enigma.out

2

Explicație

Cele două drumuri posibile sunt: (1,1) → (1,2) → (2,2) → (3,2) → (3,3) → (4,3), respectiv (1,1) → (1,2) → (3,2) → (3,3) → (4,3).

Exemplul 2:

enigma.in

5 5 4 3
0 0 1 1 1
0 0 0 0 0
0 0 0 0 0
0 1 0 1 0
0 1 1 1 0
3

enigma.out

17