## 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 i^{th} 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**