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
