题目描述

The habitants of the Byteotian Highland bred sheep for centuries.

Every sane shepherd has a fenced pasture in the shape of a convex1 polygon for the sheep to graze on.

Every sane sheep in turn has its own favourite feeding spot on the pasture where it spends all days.

Sometimes however, the sheep want to play. As they play in pairs, every shepherd keeps an even number of sheep, so that his every sheep has a partner to play with.

The shepherds are concerned about a decree recently issued by the Byteburg's High Commissioner for Agriculture.

The decree states that as of the next year the sheep can only graze on triangle-shaped pastures.

Thus every shepherd whose pasture is an -gon for is to partition it into triangles by putting fences inside.

Each single new fence, of course, is going to be a segment connecting two vertices of the polygon (pasture).

Additionally, the fences can intersect only in these vertices.

A shepherd who does not fulfil these requirements will no longer be subsidized.

Byteasar, as a shepherd, has to decide on a way of partitioning his pasture.

In fact, he is unsure how many partitions are possible. He is only interested in such partitions that no fence is drawn through a favourite spot of any sheep, and such that every resulting triangle contains the favourite spots of an even number of sheep, so that these sheep can play in pairs.

Help Byteasar by writing a program that calculates the number of such partitions!

输入格式

The first line of the standard input contains three integers , and (, , , ), separated by single spaces, that denote respectively:

the number of vertices of the polygon forming the pasture, the number of the sheep, and a certain positive integer .

Each of the following lines contains two integers and (), separated by a single space, de…

输出格式

Your program should print one integer on the standard output, namely the remainder of division by of the number of partitions of the pasture in triangles, such that no fence is drawn through a favourite spot of any sheep, and every resulting triangle contains the favourite spots of an even number of sheep.

题目大意

给一个n个点的凸多边形，再给出k个在多边形内的点，要求你把多边形划分成三角形，使得每个三角形内都有偶数个点，且三角形边上不能有点。

5 4 10
5 5
3 0
-1 -1
-3 4
1 10
1 0
-1 0
1 6
-2 5

3

提示

$4\le n\le 600$，$2\le k$，$m\le 20\ 000$，$2\mid k$，$-15\ 000\le x_i,y_i,p_i,q_i\le 15\ 000$ ，牧场的顶点坐标按顺时针顺序给出，保证羊严格在多边形内部。