teren

Înaintea Bătăliei de la Vaslui, Ștefan cel Mare are o problemă de natură spirituală. Domnitorul știe că Suleiman Pașa l-a blestemat prin diverse metode oculte, deoarece, cu două amurguri înainte de bătălie, a visat înfrângerea oștilor sale. Ştefan a decis să-l cheme pe patriarhul Nicodim al II-lea să alunge forţele răului de pe terenul de luptă, pentru a asigura victoria moldovenilor.

Terenul de luptă are forma unui poligon convex cu $N$ vârfuri $P_1, P_2, \dots, P_N$, specificate în sens trigonometric (sensul invers acelor de ceasornic) prin coordonatele lor carteziene (abscisă şi ordonată). Patriarhul poate alunga forţele răului doar dacă moldovenii vor îndeplini următoarele două condiţii:

1. vor partiţiona terenul în zone triunghiulare, prin construirea unor garduri; un gard poate să fie trasat între două vârfuri ale terenului care nu sunt vecine pe conturul terenului astfel încât oricare două garduri să nu se intersecteze în interiorul terenului;
2. cel puţin $K$ zone triunghiulare existente pe teren după partiţionare trebuie să fie sfinte.

O zonă triunghiulară cu vârfurile $A(x_A,y_A)$, $B(x_B,y_B)$, $C(x_C,y_C)$ este considerată sfântă dacă valoarea expresiei $x_A \cdot y_B + x_B \cdot y_C + x_C \cdot y_A - x_A \cdot y_C - x_B \cdot y_A - x_C \cdot y_B$ este un număr par.

Cerință

Determinaţi numărul de modalităţi distincte de a partiţiona terenul de luptă astfel încât cele două condiţii ale patriarhului Nicodim să fie respectate.

Două modalităţi sunt considerate distincte dacă există cel puţin un gard în una dintre modalităţi care nu apare în cealaltă modalitate.

Date de intrare

Fişierul de intrare teren.in conţine pe prima linie numărul natural $N$, reprezentând numărul de vârfuri ale terenului de luptă și numărul natural $K$, reprezentând numărul de zone triunghiulare sfinte care trebuie să existe pe teren. Pe următoarele $N$ linii se află câte o pereche de numere întregi $x_i\ y_i$ ($1 \le i \le N$), reprezentând abscisa, respectiv ordonata vârfurilor terenului de luptă, specificate în sensul invers acelor de ceasornic. Valorile scrise pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieșire

Fişierul de ieşire teren.out conţine o singură linie pe care este scris numărul de modalităţi distincte de a partiţiona terenul de luptă astfel încât cele două condiţii ale patriarhului Nicodim să fie respectate.

Deoarece acest număr poate fi foarte mare veţi afişa rezultatul modulo $10^9+7$.

Restricții și precizări

• $3 \le N \le 100$
• $0 \le K \le N-2$
• $-10\ 000 \le x_i, y_i \le 10\ 000$, pentru orice $1 \le i \le N$.

Exemplul 1

teren.in

5 0
1 0
3 0
5 2
4 5
0 3

teren.out

5

Explicație

Exemplul 2

teren.in

4 2
0 0
0 4
4 0
4 4

teren.out

2

Explicație

Cele două modalități sunt:

Exemplul 3

teren.in

7 3
2 0
7 0
9 3
8 5
4 7
2 6
1 3

teren.out

24

Explicație

Una dintre cele $24$ de soluții posibile este:

Triunghiurile $(P1, P2, P6)$, $(P1, P6, P7)$ și $(P2, P5, P4)$ sunt sfinte.