Страусові пристрасті
Як ви пам'ятаєте, у Джонні трапився прикрий інцидент зі страусом Чаком. Спіймавши всіх розбіглих страусів, фермер задумався про те, як би не повторити подібного безладу в майбутньому.
Джонні вирішив побудувати нове житло для птахів. Він встановив N спостережних веж з вартовими і прожекторами та з'єднав їх парканами з колючим дротом під напругою, огородивши таким чином дворик у формі багатокутника з N вершин, на якому будуть жити страуси. Для спрощення спостереження він хоче з'єднати деякі пари не сусідніх веж стінами з кулеметниками, розбивши таким чином двір на N-2 трикутних частини, що утворюють загони для страусів. Звісно, стіни повинні лежати цілком всередині багатокутника, і кожен загін повинен представляти собою невироджений трикутник, тобто його площа повинна бути ненульовою.
Зараз фермеру належить вибрати, як саме він буде розбивати двір. Допоможіть йому проаналізувати всі можливі варіанти проведення стін. Джонні цікавлять два питання — як водиться, простіше і складніше. По-перше, він хоче знати, для яких пар веж існує план розбиття, що включає стіну між ними. По-друге, його цікавить, скільки взагалі існує планів розбиття двору.
Вхідні дані
У першому рядку вхідного файлу йде число N (3 ≤ N ≤ 300) — кількість веж.
У наступних N рядках дано описи веж за порядком їх обходу. i-й рядок містить два цілих числа x_i, y_i, за модулем не перевищують 10^4 — координати i-ї вежі.
Гарантується, що двір представляє собою багатокутник ненульової площі без самодотиків і самоперетинів.
Вихідні дані
У першому рядку виведіть K — кількість пар веж, між якими потенційно може бути проведена стіна.
Далі виведіть K пар номерів веж по одному в кожному рядку. Числа в кожній парі повинні бути впорядковані за зростанням, пари повинні йти спочатку за зростанням перших чисел, потім за зростанням других чисел.
Останній рядок повинен містити єдине число — кількість способів поділити двір на загони. Оскільки воно може бути досить великим, виведіть залишок від його ділення на 2^30 = 1073741824.