Sheep

Memory limit: 32 MB

The habitants of the Byteotian Highland bred sheep for centuries. Every sane shepherd has a fenced pasture in the shape of a convex¹ 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!

Input

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, denoting the coordinates of the -th vertex of the pasture. The vertices are given in a clockwise order. Each of the lines that follow holds two integers , (), separated by a single space, denoting the coordinates of the favourite spot of the -th sheep. All the favourite spots lie strictly inside (i.e., not on the boundary) the pasture.

Output

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.

Example

For the input data:

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

the correct result is:

3

The figure depicts three possible partitions into triangles. The favourite spots of the sheep are marked with dots.

Task author: Michal Wlodarczyk.