Bürc#1912
Tədqiqatçılar yaxınlarda qədim bir əlyazmanın tapıntısı nəticəsində müəyyən bir bürcü təsvir edən məlumat əldə ediblər. Əlyazmaya görə, bürc ulduzdan ibarətdir və səmanı müstəvi kimi nəzərdən keçirsək, ulduzlar bu müstəvidə nöqtələr kimi qəbul edilir və bütün ulduz cütləri arasındakı məsafələr məlumdur.
Bu bürcün ehtimal olunan yerləşdiyi səma yarımkürəsində bu gün ulduz görünür. Adətən bürc dedikdə səmanın bir hissəsindəki ən parlaq ulduzların birləşməsi nəzərdə tutulur, amma minilliklər ərzində ulduzların parlaqlığı dəyişə bilərdi və buna görə də bu kriteriya artıq etibarlı deyil. Beləliklə, bu gün səmanın hansı ulduzlarının əlyazmada təsvir olunan bürcü təşkil edə biləcəyini yalnız məsafə məlumatlarına əsaslanaraq müəyyən etmək olar.
Bürcün mümkün yerləşməsi deyəndə, (I_1, I_2, \ldots, I_M) ardıcıllığı nəzərdə tutulur ki, hər bir və üçün (1 \leq i, j \leq M), I_i və I_j ulduzları arasındakı məsafə, əlyazmadakı -ci və -ci ulduzlar arasındakı məsafəyə bərabər olsun. İki mümkün yerləşmə fərqlidir, əgər heç olmasa bir mövqedə fərqli ulduzlar varsa.
Sizə bu gün səmanın ulduzlar dəstəsi verilir. Həmçinin, M \times M ölçülü bir matrisa verilir, burada elementi bürcdəki və ulduzları arasındakı məsafənin kvadratını göstərir. Bu bürcün mümkün yerləşmələrinin sayını hesablayın.
Birinci sətirdə ədədi verilir. Sonra sətirdə hər biri tam ədəd olan məsafələr matrisası verilir. Sonra ədədi, ardınca isə sətirdə X_i, Y_i — bu günkü səmanın -ci ulduzunun koordinatları qeyd olunur.
2 \leq N \leq 30000, 2 \leq M \leq \min(N, 20).
Hər bir ulduzun koordinatları modulu -dən çox olmayan tam ədədlərdir. Heç bir iki ulduz eyni nöqtədə yerləşmir.
Verilən məsafələr matrisası simmetrikdir, əsas diaqonalında yalnız sıfırlar, digər bütün elementlər isə 10^{18}-dən böyük olmayan müsbət tam ədədlərdir.
Əlyazmada təsvir olunan bürcün mümkün yerləşmələrinin sayını çıxarın.
Nümunə 1