점화식

정수 튜플 $P = (P_1, P_2, P_3, \dots, P_n)$이 주어진다. 이 튜플에 대한 함수 $F$를 다음 세 규칙으로 정의한다.

$P_i$ 중 하나라도 음수이거나 $P_1 \ge P_2 \ge \dots \ge P_n$이 성립하지 않으면 $F(P) = 0$이다.

$P = (0, 0, \dots, 0)$이면 $F(P) = 1$이다.

그 밖의 경우에는 좌표 하나를 골라 1을 뺀 튜플 $n$개의 함숫값을 모두 더한다.

$F(P_1, P_2, \dots, P_n) = \sum_{k=1}^{n} F(P_1, \dots, P_k - 1, \dots, P_n)$

$n = 4$인 경우를 보자. $F(4, 3, 2, -1)$은 마지막 좌표가 음수이므로 0이다. $F(4, 3, 2, 5)$는 좌표가 큰 수부터 작은 수 순서로 놓여 있지 않으므로 0이다. $F(4, 3, 2, 1)$은 $F(3, 3, 2, 1) + F(4, 2, 2, 1) + F(4, 3, 1, 1) + F(4, 3, 2, 0)$이다.

튜플 $P$가 주어지면 $F(P_1, P_2, \dots, P_n)$을 구하라. 값이 매우 커질 수 있으므로 소수 1,000,000,009로 나눈 나머지를 출력한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스는 두 줄이다. 첫째 줄에 $n$이 주어지고, 둘째 줄에 공백 하나로 구분된 정수 $n$개가 주어진다. 이 수가 튜플 $P$다.

$1 \le n \le 1000$이고 $1 \le P_i \le 1000$이다. $P$는 $P_1 \ge P_2 \ge \dots \ge P_n$을 만족한다.

각 테스트 케이스마다 Case #x: R 형식으로 한 줄씩 출력한다. $x$는 테스트 케이스 번호이고 1부터 시작한다. $R$은 $F(P_1, P_2, \dots, P_n)$을 1,000,000,009로 나눈 나머지다.