题目描述

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.

题目大意

题目描述

译自 POI 2010 Stage 2. Day 2「Sheep」

Byteasar 有一个凸多边形牧场，里面有一些羊。
现在 Byteasar 想要把这个凸多边形划分成若干三角形（划分线不能在牧场中相交，只能在顶点相交），使得每一个三角形里面的羊都有偶数只。
Byteasar 想知道有多少种方案，你只要输出方案数对 $m$ 取余后的结果即可。

输入格式

第一行三个空格隔开的正整数 $n,k,m$ ，分别表示牧场的顶点数，羊的个数，以及模数。
接下来 $n$ 行，每行两个空格隔开的正整数 $x_i,y_i$ ，表示牧场的顶点坐标。
接下来 $k$ 行，每行两个空格隔开的正整数 $p_i,q_i$ ，表示羊的坐标。

输出格式

一行一个整数，表示方案数对 $m$ 取模的结果。

翻译来自于 LibreOJ。

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$ ，牧场的顶点坐标按顺时针顺序给出，保证羊严格在多边形内部。