Zalım Bingo#3550
Bingo, bir çox oyunçu və bir oyun ustası tərəfindən oynanan əyləncəli bir oyundur. Hər bir oyunçuya N^2 fərqli nömrədən ibarət N×N ölçülü bir bingo kartı verilir (adətən N = 5). Oyun zamanı usta lotereyadan nömrələri bir-bir çəkir. Hər dəfə bir nömrə çəkildikdə, oyunçular həmin nömrə kartlarında varsa, onu işarələyirlər. Oyunçunun məqsədi bir vertikal, horizontal və ya diaqonal xəttdə N işarələnmiş kvadrat əldə etmək və sonra "Bingo!" deməkdir. İlk "Bingo!" deyən oyunçu oyunu qazanır.
Ən bədbəxt hallarda, kartda dəqiq N işarələnməmiş kvadrat və ya N(N-1) işarələnmiş kvadrat ola bilər, lakin bingo nümunəsi olmaz. Bu məsələdəki vəzifəniz, sıfır və ya daha çox işarələnmiş kvadratları olan verilmiş başlanğıc nümunəsindən neçə belə nümunənin mümkün olduğunu sayan bir proqram yazmaqdır.
Giriş aşağıdakı formatda verilir:
N K x_1 y_1 ... x_K y_K
Giriş, bingo kartının ölçüsünü və başlanğıc nümunəsindəki işarələnmiş kvadratların sayını göstərən iki ədəd N (1 ≤ N ≤ 32) və K (0 ≤ K ≤ 8) ilə başlayan bir sətirdən ibarətdir. Sonra K sətir gəlir, hər biri (x_i, y_i) kvadratının işarələndiyini göstərmək üçün iki ədəd x_i və y_i ehtiva edir. Koordinat dəyərləri sıfırdan başlayır (yəni 0 ≤ x_i, y_i ≤ N-1). İşarələnmiş kvadratların heç bir cütü üst-üstə düşmür.
Verilmiş başlanğıc nümunəsindən dəqiq N işarələnməmiş kvadrat olan mümkün qeyri-bingo nümunələrinin sayını sayın və nəticəni 10007 modulu ilə bir sətirdə çap edin (çünki bu, çox böyük ola bilər). Döndərilmiş və ya aynalanmış nümunələr fərqli hesab edilməli və hər biri sayılmalıdır.
Nümunə 1