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 First line of the input contains an integer T (1 ≤ T ≤ 85), the number of test cases. Each case starts with an integer Nonaline(N=|S|,3≤N≤1,000). NextNlines 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 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). 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 . Sample Input 1 3 00 10 01 2 Sample Output 1