Bürclər
Tədqiqatçılar yaxınlarda bəzi bürcləri təsvir edən qədim bir əlyazma tapıblar. Bu əlyazmadan məlum olur ki, bürc M ulduzdan ibarətdir. Səmanı müstəvi, ulduzları isə bu müstəvidəki nöqtələr kimi nəzərdən keçirdikdə, bürcdəki hər bir ulduz cütü arasındakı məsafələr məlumdur.
Bu günkü səmanın həmin bürcün ehtimal olunan yerləşdiyi yarımkürəsində N ulduz görünür. Adi bürc səmanın hər hansı bir hissəsinin ən parlaq ulduzlarının birləşməsi hesab olunur. Lakin keçən minilliklər ərzində ulduzların parlaqlığı dəyişə bilərdi, buna görə də bu göstəriciyə əsaslanmaq artıq mümkün deyil. Buna görə də, bu günkü səmanın hansı ulduzlarının əlyazmada təsvir edilən bürcü təşkil edə biləcəyini müəyyən etmək yalnız məsafə məlumatlarına əsaslanmalıdır.
Bürcün mümkün yerləşməsi adlandıracağıq ulduzların (I_1, I_2, ..., I_M) siyahısını, belə ki, hər bir i və j (1 ≤ i, j ≤ M) üçün I_i və I_j ulduzları arasındakı məsafə əlyazmadakı i-ci və j-ci ulduzlar arasındakı məsafəyə bərabərdir. İki mümkün yerləşmə fərqlidir, əgər heç olmasa bir mövqedə fərqli ulduzlar yazılıbsa.
Sizə bu günkü səmanın ulduzlar dəstəsi verilir. Həmçinin, MxM ölçülü bir matrisa verilir, burada (i, j) elementi bürcdəki i və j 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.
Giriş verilənləri
Giriş faylının ilk sətiri M ədədini ehtiva edir. Növbəti M sətir hər biri M tam ədəd ehtiva edir — məsafələr matrisası. Daha sonra N ədədi yazılır və sonra N sətir gəlir, hər biri bu günkü səmanın i-ci ulduzunun koordinatlarını göstərən X_i, Y_i tam ədədlər cütünü ehtiva edir.
2 ≤ N ≤ 30000, 2 ≤ M ≤ min(N, 20).
Hər bir ulduzun koordinatları mütləq qiymətcə 10000-i keçməyən tam ədədlərdir. Heç bir iki ulduz eyni nöqtədə yerləşmir.
Verilən məsafələr matrisası simmetrikdir, onun əsas diaqonalı yalnız sıfırları ehtiva edir və bütün digər ədədlər müsbətdir və 10^18-i keçmir.
Çıxış verilənləri
Əlyazmadakı bürcün mümkün yerləşmələrinin sayını çıxarın.