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.