题目描述

译自 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$ 取模的结果。

样例

输入

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

输出

3

数据范围与提示

对于 $100$ 的数据，$4≤n≤600$，$2≤k,m≤20000$，$-15000≤xi,yi,pi,qi≤15000$，牧场的顶点坐标按顺时针顺序给出，保证羊严格在多边形内部。