Tarix#11540
Artyom adlı bir oğlan var idi. Bir gün Artyom xoşbəxtlik axtarışına çıxdı.
Artyom uzun müddət yol getdi və hava qaralana qədər dayanmadan irəlilədi. Bu qaranlıqda bir Əjdaha yatırdı. Əjdaha ağ daşlarla əhatə olunmuşdu. Artyom "Əjdahanı necə tutmaq olar" kitabından öyrənmişdi ki, bəzi daşları elə rəngləməlidir ki, əjdaha rənglənmiş daşların içində qalsın. Əjdaha bu şəkildə tutulacaq. Hər daş iki vəziyyətdə ola bilər: rənglənmiş və ya rənglənməmiş.
Daşları konveks çoxbucaqlının zirvələri kimi təsəvvür etmək olar, əjdahanı isə nöqtələr dəsti kimi. Sizin vəzifəniz, əjdahanı tutmaq üçün daşları rəngləmək yollarını hesablamaqdır.
Birinci sətir iki tam ədəd və m~(3 \le n \le 5000, 0 \le m \le 5000) ehtiva edir.
Növbəti sətir hər biri iki tam ədəd ehtiva edir - konveks çoxbucaqlının zirvələrinin koordinatları. Onların ya saat əqrəbi istiqamətində, ya da əks istiqamətdə verildiyi və heç bir üç nöqtənin eyni düz xətt üzərində olmadığı təmin edilir.
Növbəti sətir əjdahaya aid nöqtələri müəyyən edir. Hər biri iki tam ədəd ehtiva edir - əjdahanın koordinatları, modulu 10^9-u keçmir.
Cavabı 10^9 + 7 modulu ilə çıxarın.
m = 0 olduqda, öz içində boş olmayan bir sahə ehtiva edən hər hansı bir daş alt dəstini rəngləyə bilərsiniz.
Daşların hər hansı bir alt dəstini rəngləmək lazımdır ki, onların konveks qabığı bütün əjdaha nöqtələrini əhatə etsin və öz içində boş olmayan bir sahə ehtiva etsin (daşlar ən azı 3 olmalıdır). Əjdaha nöqtəsi konveks qabığın sərhədində yerləşirsə, onu örtülmüş hesab edirik.
Nümunə 1
Nümunə 2