Cerința

Pentru a evada (din nou) din Matrix, Neo trebuie să străbată un labirint reprezentat de o matrice cu n linii și m coloane. Fiecare celulă a labirintului este marcată cu o cifră în baza 10. Pozițiile marcate prin cifre pare pot fi parcurse de Neo, iar cele marcate cu cifre impare nu, deoarece acolo sunt agenți ai lui Mr. Anderson. De asemenea, Neo nu poate să treacă de mai multe ori prin aceeași celulă, deoarece ar fi descoperit de către Mr. Anderson. Inițial, Neo se află în celula de coordonate (x, y), cunoscută, iar pentru a putea evada, Neo trebuie să străbată exact z celule ale labirintului.

Pentru a deruta agenții lui Mr. Anderson Neo se poate deplasa doar pe valori vecine pe diagonale. Dacă se află în poziția (i,j), atunci el poate merge în pozițiile (i-1,j-1), (i+1,j+1), (i-1,j+1) și (i+1,j-1).

Neo vrea să știe numărul total de moduri în care poate parcurge labirintul. Dacă îl ajutați să calculeze acest număr, atunci Neo va insista pe lângă Morpheus să vă aducă bomboane roșii și albastre.

Date de intrare

Se citește de la tastatură numerele n și m, iar de pe următoarele n linii câte m valori cu semnificația din enunț, separate prin câte un spațiu. Apoi se citesc poziția (x,y) și numărul de celule z prin care trebuie să treacă Neo.

Date de ieșire

Se va afișa pe ecran numărul de moduri în care Neo poate parcurge labirintul, pornind din poziția inițială, mergând doar prin celule marcate cu numere pare, fără să treacă de mai multe ori prin aceeași celulă și trecând prin exact z celule.
Dacă Neo nu poate parcurge labirintul, atunci se va afișa mesajul Mr. Anderson wins!

Restricții și precizări

• 1 ≤ n,m ≤ 10
• elementele matricii sunt cuprinse între 0 și 9
• poziția (x,y) are valoare pară

Exemplu:

Intrare

4 5
8 6 0 3 4
0 4 4 2 1
7 5 2 3 2
4 3 9 0 3
2 2 5

Ieșire

4

Explicație

Cele 4 trasee de lungime 5 sunt:

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

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

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

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