Straus ehtirasları#5774
Johnny son vaxtlar Çak adlı dəvəquşusuyla bir hadisə yaşadı. Qaçan dəvəquşuların hamısını topladıqdan sonra, fermer gələcəkdə belə qarışıqlığın qarşısını necə almağı düşündü.
Johnny quşlar üçün yeni məskən tikməyə qərar verdi. O, hər birinə proyektorlar quraşdırılmış nəzarət qülləsi tikdi və onları elektrikləşdirilmiş tikanlı məftil hasarları ilə birləşdirdi. Bu quruluş, dəvəquşuların qalacağı həyəti zirvəli çoxbucaqlı şəklində hasara aldı. Nəzarəti asanlaşdırmaq üçün o, qeyri-bitişik qüllə cütlərini arakəsmə divarlarla birləşdirməyi planlayır və bununla həyəti N-2 üçbucaqlı sahəyə bölür, hər birinə dəvəquşu üçün bir məskən yaranır. Əsas odur ki, bu divarlar tamamilə çoxbucaqlının daxilində olmalı və hər bir məskən sıfır olmayan sahəyə malik qeyri-degenerasiya olunmuş üçbucaq olmalıdır.
Fermer indi həyəti necə bölmək barədə qərar verməlidir. Ona bütün mümkün divar düzülüşlərini təhlil etməkdə kömək edin. Johnny iki sualla maraqlanır — biri daha asan, biri isə daha çətindir. İlk olaraq, hər hansı bölünmə planında aralarında divar çəkilə biləcək qüllə cütlərini bilmək istəyir. İkinci sualı isə bütün mümkün bölünmə planlarının sayıdır.
Giriş faylının ilk sətrində (3 \leq N \leq 300) — qüllələrin sayı verilir.
Sonrakı sətrin hər birində qüllələrin ardıcıllıqla təsviri verilir. -ci sətrdə iki tam ədəd x_i, y_i (|x_i|, |y_i| \leq 10^4) — -ci qüllənin koordinatları göstərilir.
Zəmanət verilir ki, həyətyanı sahə öz-özünə toxunmayan və kəsişməyən, sıfır olmayan sahəli çoxbucaqlıdır.
Birinci sətirdə — aralarında potensial olaraq divar çəkilə biləcək qüllə cütlərinin sayı çıxarılmalıdır.
Sonra sətrin hər birində belə cütlər ardıcıllıqla — əvvəlcə birinci, sonra ikinci qüllənin nömrəsi artan qaydada, cütlər isə əvvəlcə birinci, sonra ikinci ədəddən asılı olaraq sıralanmış formada verilməlidir.
Sonuncu sətirdə həyəti məskənlərə bölməyin mümkün planlarının sayı verilməlidir. Bu ədəd çox böyük ola bilər, ona görə 2^{30} = 1073741824 modulu üzrə verilməlidir.
Nümunə 1