Avem o jucărie formată din NxN
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 doua, coloana N-1
, linia N-1
, coloana 2
etc. Sunt [N/2]
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 de intrare 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 de ieșire 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 9901
.
Restricții și precizări
3 ≤ N ≤ 999
,N
este impar0 ≤ P ≤ 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)
.