Problem C: Counting P-Hulls

Let S be a set of N points in Euclidean plane such that no three points are co-linear and let P be one of the N points in the set S. A subset X of S generates a P-hull if X contains at least 3 points and if the convex hull of X contains P on its boundary. Count the number of subsets of S that generate a P-hull.

Input Format

First line of the input contains an integer T (1 ≤ T ≤ 20), the number of test cases. Each case starts with an integer N on a line (N = |S|, 3 ≤ N ≤ 1,000). Next N lines contain two integers each, X and Y, the coordinates of the ith point (1 ≤ i ≤ N, |X|,|Y| ≤ 10,000). Last line of the test case contains a single integer K, the index of our point P (1 ≤ K ≤ N).

Output Format

For each test case, print the number of subsets of S that generate a P-hull. Output the count mod 1,000,000,009 (i.e., the remainder of dividing the answer by this number).

Sample Input

1
3
0 0
1 0
0 1
2

Sample Output

1

In Case You Do Not Know:

The convex hull of a set Y in the Euclidean plane is the smallest convex set that contains Y.
An object is a convex set if for every pair of points within the object, the line connecting those points is fully inside the object.
The convex hull may be visualized as the shape formed by a rubber band stretched around the points in Y.


Darcy Best
ACPC 2013