cubic

Avem o jucărie formată din $N \times N$ pătrate de latură $1$ dispuse ca într-o matrice cu $N$ linii și $N$ coloane. Liniile și coloanele matricei sunt numerotate de la $1$ la $N$, iar $N$ este mereu impar. Pătrățelele pot fi albe și le vom codifica $0$, sau negre și le codificăm $1$. Împărțim matricea în zone concentrice astfel: zona $1$ este formată din linia $1$, coloana $N$, linia $N$ și coloana $1$; zona $2$ este formată din linia a $2$-a, coloana $N - 1$, linia $N - 1$, coloana $2$ etc. Sunt $\lfloor \frac{N}{2} \rfloor$ astfel de zone. În mijlocul matricei este, evident, un singur element, $N$ fiind impar. Asupra oricărei zone putem aplica o operație de rotire, doar spre stânga. Iată în figura de mai jos efectul unei operații de rotire "de lungime" $3$, asupra unei zone.

În figurile de mai jos culorile de fundal ale pătrățelelor au doar rolul de a pune în evidență zonele (cu gri închis este zona $1$ și cu gri mai deschis zona $2$). Dorim să aplicăm asupra jucăriei un set de rotiri așa încât "să rezolvăm jucăria". Asta înseamnă că toate pătrățelele de pe linia din mijloc și cele de pe coloana din mijloc să devină negre.

Observăm în figura din dreapta că linia $3$ și coloana $3$ sunt pline de $1$. Pentru aceasta, am aplicat o rotire de lungime $2$ asupra zonei $1$ și o rotire de lungime $0$ asupra zonei $2$. Codificăm această soluție cu ($2, 0$). Altă soluție este cea codificată prin ($2, 2$).

Cerința

Dată fiind codificarea jucăriei, precum și "lungimea" maximă permisă pentru o rotire în oricare zonă, să se determine numărul de posibilități de a aplica rotiri asupra zonelor așa încât să rezolvăm jucăria. Evident, unei zone i se poate aplica o singură rotire, de lungime cuprinsă între $0$ și valoarea maximă permisă.

Date de intrare

Fișierul cubic.in conține pe prima linie două numere $N$ și $P$, separate printr-un spațiu, reprezentând dimensiunea jucăriei respectiv lungimea maximă permisă pentru rotirile din oricare zonă. Pe fiecare din următoarele $N$ linii se află câte $N$ numere care pot fi $0$ sau $1$, neseparate de spații.

Date de ieșire

Fișierul cubic.out conține pe prima linie numărul de posibilități de a aplica rotiri asupra zonelor, pentru a rezolva jocul. Două posibilități se consideră distincte dacă diferă prin lungimea rotirii din cel puțin o zonă. Pentru că acest număr poate fi foarte mare, se va afișa restul împărțirii lui la $9 \ 901$.

Restricții și precizări

• $3 \leq N \leq 999$, $N$ este impar.
• $0 \leq P \leq 100 \ 000$;

Exemplu

cubic.in

5 3
11001
00111
11111
11111
11111

cubic.out

4

Explicație

Soluțiile sunt $(2, 0)$, $(3, 0)$, $(2, 2)$, $(3, 2)$.