Chef has a Spaghetti Garden

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef is tending a really large spaghetti garden. This garden consists of many spaghetti trees. Specifically, there is a spaghetti tree planted for each lattice point location (x, y) with x, y ≥ 0. (Yes, there are an infinite number of trees in Chef's garden!)
It's the 1st of April, so it's harvest time for Chef. Chef plans to harvest all spaghetti strands within a certain region today. In case you didn't know, a spaghetti tree bears spaghetti strands as its fruits.
Specifically, Chef plans to harvest all spaghetti strands hanging from every spaghetti tree whose location (x, y) is within the interior or boundary of a certain polygon with N vertices. Also, the spaghetti tree located at (x, y) currently bears exactly F_{x+y} fruits, where F_{k} satisfies the following fourthorder recurrence:
F_{k} = a·F_{k1} + b·F_{k2} + c·F_{k3} + d·F_{k4}
How many strands of spaghetti will Chef be able to harvest today? Since this number can be very large, output it modulo 10^{9} + 9. (Note: this is slightly different from the usual mod.)
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains nine space separated integers N, a, b, c, d, F_{0}, F_{1}, F_{2}, and F_{3}.
After that, N lines follow. The i^{th} line contains two integers x_{i} and y_{i}, denoting that (x_{i}, y_{i}) is the i^{th} vertex of the polygon in counterclockwise order.
Output
For each test case, output a single line containing the integer: the answer for that test case.
Constraints
 0 ≤ a, b, c, d, F_{0}, F_{1}, F_{2} F_{3} < 10^{9} + 9
 The polygon is simple and nondegenerate.
 1 ≤ T ≤ 2000
 3 ≤ N ≤ 16
 The sum of the N in a single test file is ≤ 6000
Subtasks
Subtask #1 (10 points): 0 ≤ x_{i}, y_{i} ≤ 100
 0 ≤ x_{i}, y_{i} ≤ 10^{4}
 0 ≤ x_{i}, y_{i} ≤ 10^{9}
Example
Input: 2 4 1 2 3 4 0 1 2 3 1 1 2 1 2 2 1 2 4 1 2 3 4 0 1 2 3 1 1 3 1 3 3 1 3 Output: 18 153
Explanation
In both test cases, we have F_{k} = k for 0 ≤ k ≤ 3 and F_{k} = F_{k1} + 2·F_{k2} + 3·F_{k3} + 4·F_{k4}. So you can check that F_{4} = 10, F_{5} = 26 and F_{6} = 63
 In the first test case, Chef will harvest all spaghetti strands in the locations (1, 1), (1, 2), (2, 1), (2, 2). The total number is F_{1+1} + F_{1+2} + F_{2+1} + F_{2+2} = F_{2} + F_{3} + F_{3} + F_{4} = 18
 In the second test case, Chef will harvest all spaghetti strands in the locations (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3). The total number is F_{1+1} + F_{1+2} + F_{1+3} + F_{2+1} + F_{2+2} + F_{2+3} + F_{3+1} + F_{3+2} + F_{3+3} = F_{2} + F_{3} + F_{4} + F_{3} + F_{4} + F_{5} + F_{4} + F_{5} + F_{6} = 153
Author:  kevinsogo 
Tester:  dpraveen 
Tags  kevinsogo 
Date Added:  14072015 
Time Limit:  9 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 