Triangulation of Pasture

In the Byteotian Highland, each shepherd owns a convex polygonal pasture with n vertices and an even number of sheep. Every sheep has its own favorite feeding spot (a point strictly inside the polygon). Due to a new decree, the pasture must be partitioned (triangulated) into triangles by drawing diagonals (segments connecting two non‐adjacent vertices) that do not intersect except at the vertices. Furthermore, no newly drawn fence (diagonal) is allowed to pass through any sheep’s favorite spot. Finally, in every resulting triangle the number of favorite spots that lie strictly inside must be even, so that the sheep in that triangle can play in pairs.

Formally, given a convex n-gon with vertices (ordered either clockwise or counterclockwise) and m favorite points inside it, you are to count the number of ways to partition the polygon into triangles (i.e. to choose a set of diagonals such that the interior is tiled by triangles) subject to the following constraints:

• Each diagonal is a segment connecting two vertices. For any diagonal that is drawn (i.e. not a boundary edge), no favorite point lies exactly on it.
• For every triangle in the partition, if we let f be the number of favorite points that lie strictly inside the triangle, then f must be even.

If the polygon is already a triangle (n = 3), then no diagonal is drawn; however, the triangle is accepted only if it contains an even number (possibly 0) of favorite spots.

Notes:

• The standard fact that a convex n-gon can be partitioned into n-2 triangles by drawing exactly n-3 diagonals holds.
• Any segment connecting two consecutive vertices (or the edge connecting the first and the last vertex) is considered a boundary edge and is always valid.
• All favorite points are given in the interior of the polygon and no two points coincide.

Your task is to calculate the number of valid partitions.

The formulas used in the solution include:

• The total number of triangles in any triangulation is always $n-2$.
• The DP recurrence, if we denote by $dp[i][j]$ the number of valid triangulations of the subpolygon with vertices $i, i+1, \ldots, j$, is given by \[ dp[i][j] = \sum_{k=i+1}^{j-1} \left(dp[i][k] \cdot dp[k][j]\right), \] provided that the triangle formed by vertices $i$, $k$, and $j$ contains an even number of favorite points and the used diagonals do not pass through any favorite point.

inputFormat

The first line contains two integers n and m ($3 \le n \le N$, m is even, and m ≥ 0), denoting the number of vertices of the convex polygon and the number of favorite feeding spots respectively.

The next n lines each contain two integers x and y, representing the coordinates of the polygon vertices given in order (either clockwise or counterclockwise).

The following m lines each contain two integers x and y, representing the coordinates of the favorite feeding spots.

outputFormat

Output a single integer — the number of valid triangulations (i.e. partitions) of the pasture satisfying the conditions.

sample

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

1