Kites
Зимни Състезания по Информатика, 2017
Time Limit: 2s, Memory Limit: 128MiB
Докато разглеждаше снимките от детството си, Ели попадна на една, в която тя и N – 1 нейни приятели се бяха наредили в редичка и управляваха по едно хвърчило. За съжаление, Ели вече не помни кое хвърчило принадлежеше на кой от приятелите й. Единственото, което помни, е че въжетата на хвърчилата не се преплитаха (иначе биха се оплели и паднали). Сега момичето се зачуди колко възможни конфигурации на хвърчилата има - тоест по колко различни начина може всяко дете да държи по едно хвърчило, така че въжетата им да не се преплитат. Ще представим всяко дете като точка с координати (Ci, 0) (тъй като са на земята), докато хвърчилата като точка (Xi, Yi) (тъй като летят). Въжето на хвърчилото на всяко дете е отсечката, свързваща координатите на детето с координатите на хвърчилото му. Реално Ели се интересува от броя пермутации на хвърчилата P, така че ако дете i държи хвърчило Pi, никои две от образуваните отсечки да не се пресичат или докосват.
Вход
На първия ред на стандартния вход ще бъде зададено едно цяло число N – броя деца и хвърчила. На следващия ред ще има N на брой цели числа Ci – позициите на всяко от децата по абсцисата. Следват N реда с по две цели числа Xi и Yi - координатите на всяко от хвърчилата.
Изход
На единствен ред на стандартния изход изведете едно цяло число – броя валидни конфигурации на хвърчилата. Тъй като този брой може да бъде много голям, изведете само остатъка му при деление на 1,000,000,007.
Ограничения
  • 1 ≤ N ≤ 50
  • 1 ≤ Ci, Xi, Yi ≤ 5,000
Примерен Вход Примерен Изход
5 42 13 17 5 666 77 13 19 101 55 82 1 80 55 133 3
Мрън!