Історія#11540
Жив-був хлопчик на ім'я Артем. Одного разу він вирушив на пошуки щастя.
Артем йшов і йшов, поки не стемніло. У цій темряві він натрапив на сплячого Дракона, оточеного білими каменями. З книги "Як спіймати дракона" Артем знав, що деякі з цих каменів потрібно розфарбувати так, щоб дракон опинився всередині розфарбованих каменів. Після цього дракон буде спійманий. Кожен камінь може бути в одному з двох станів: розфарбований або не розфарбований.
Камені можна уявити як вершини опуклого багатокутника, а дракона — як набір точок. Ваше завдання — підрахувати, скільки існує способів розфарбувати камені так, щоб спіймати дракона.
Перший рядок містить два цілі числа і m~(3 \le n \le 5000, 0 \le m \le 5000).
Наступні рядків містять по два цілі числа — координати вершин опуклого багатокутника. Гарантується, що вони задані або за годинниковою стрілкою, або проти годинникової стрілки, і жодні три точки не лежать на одній прямій.
Наступні рядків задають точки, що належать дракону. Кожна з них містить по два цілі числа — координати дракона, які не перевищують за модулем 10^9.
Виведіть відповідь за модулем 10^9 + 7.
При m = 0 ви можете розфарбувати будь-яку підмножину каменів, яка всередині себе містить непорожню область.
Розфарбовувати слід будь-яку підмножину каменів, щоб їх опукла оболонка покривала всі точок дракона і містила всередині себе непорожню область (камінців має бути як мінімум 3). Якщо точка дракона лежить на межі опуклої оболонки, то вважаємо її покритою.
Приклад 1
Приклад 2