Sequence III

Accepts: 1
Submissions: 15
Time Limit: 6000/3000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
Jinye is playing with cards. He has n cards in hand now. There is a number range from 1 to m writing on each card respectively. There is a card sequence in the deck. At the beginning the sequence is empty. Jinye will play for t rounds, at each round, Jinye will play one of these two operations: 1. select x y. x and y are both integer and x should between 1 and the number of cards in Jinye¡¯s hand now, y should between 1 and the number of cards in the card sequence+1.That means Jinye insert the $x_{th}$ card in his hand into the card sequence¡¯s $y_{th}$ position. For example, if the cards in Jinye¡¯s hand is 2,3,3,6,1 now, and the card sequence is 2,2,5,4,3, after we play ¡°select 4 2¡±, the cards in Jinye¡¯s hand become 2,3,3,1, and the card sequence become 2,6,2,5,4,3. 2. pop. Pop up the cards in the card sequence¡¯s right most and put it into the right most of Jinye¡¯s hand. For example, if the cards in Jinye¡¯s hand is 2,3,3,1 now, and the card sequence is 2,6,2,5,4,3, after we play ¡°pop¡±, the cards in Jinye¡¯s hand become 2,3,3,1,3 and the card sequence become 2,6,2,5,4. The card sequence should be empty after t rounds. For the card with number i writing on it, if it¡¯s in card sequence now, its position in card sequence should never exceed $h_{i}$ at any moment. There are some limits between cards. If x is limited by y, that means if there is at least one card with number y in the card sequence now, the card with number x can not be insert into the card sequence. Note that x can be equal to y, that means there is at most one x in the card sequence. If there is no card can be insert into card sequence, the ¡°select x y¡± operation is illegal. If there is no card in the card sequence now, the ¡°pop¡± operation is illegal. Our problem is, how many legal operate sequence can meet all the demand. Two operate sequences are consider different if there is a round they display different operations or there is a round they both display ¡°select¡± but the parameters are different. Output the answer modulo 1000000009.
Input
The first line contains a single integer T, indicating the number of test cases. Each test case begin with three integers n, m, and t, indicating the number of cards in Jinye¡¯s hand now, the range of the number writing on card, the number of rounds this game will play. Next line contain n integers $A_{1},A_{2}, \ldots, A_{n}, A_{i}$ means the number writing on the $i_{th}$ cards. Next line contain m integers $h_{1},h_{2}, \ldots, h_{m}$, as described above. Next line contain an integers f, indicating the number of limits between cards. Next f lines, each line contains two integers x and y, means x is limited by y. [Technical Specification] 1 <= T <= 30 1 <= n <= 15 1 <= m <= 15 1 <= t <= 30,t is even 1 <= $A_{i}$ <= m 1 <= $h_{i}$ <= t 0 <= f <= m*m 1 <= x,y <= m
Output
For each case, output contain one line, the number of answer.
Sample Input
1
1 1 2
1
1
0
Sample Output
1