이야기를 하나 들려줄게 (스몰)

한 이야기꾼이 옛날 이야기의 결말을 말할 때마다 다르게 기억한다.

타이론 왕에게 대신이 네 명 있었다. 서열이 높은 쪽부터 주급이 금화 7개, 4개, 6개, 6개였다. 급여 명단이 신문에 실리자 둘째 대신이 자기보다 서열이 낮은 대신의 급여가 더 높다며 항의했다. 왕은 급여도 서열도 손대지 않고 대신 한 명을 해고했다. 한 판본에서는 셋째 대신을 해고하고 이어서 넷째 대신을 해고했다. 다른 판본에서는 항의와 아무 상관이 없는 첫째 대신을 먼저 해고했고, 항의가 그대로 남아 있어서 둘째 대신도 해고했다. 두 판본의 결말은 같다. 남은 대신의 급여가 서열이 높은 쪽부터 읽을 때 한 번도 올라가지 않게 되어 아무도 항의하지 않고 해고가 멈춘다.

이야기꾼은 해고 순서를 더는 기억하지 못하고 규칙만 기억한다. 대신은 $N$명이고 서열이 높은 쪽부터 $1$번부터 $N$번까지 번호를 매긴다. $i$번 대신의 주급은 $a_i$이다. 재직 중인 대신 가운데 $i < j$이면서 $a_i < a_j$인 쌍이 하나라도 있으면 항의가 나온다. 항의가 남아 있는 동안 왕은 재직 중인 대신 가운데 정확히 한 명을 해고한다. 누구를 해고할지는 왕의 자유이고, 어떤 항의와도 관계가 없는 대신을 해고할 수 있다. 남은 대신끼리의 서열 순서는 그대로 유지된다. 재직 중인 대신의 급여가 서열이 높은 쪽부터 읽을 때 한 번도 올라가지 않게 되면 항의가 사라지고 해고가 끝난다.

이야기 하나는 해고된 대신을 해고된 순서대로 나열한 수열이다. 두 이야기는 이 수열이 서로 다를 때 다른 이야기다. 처음부터 아무도 항의하지 않으면 아무도 해고되지 않고, 빈 수열 하나가 유일한 이야기다. 이야기꾼이 들려줄 수 있는 이야기의 개수를 10007로 나눈 나머지를 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에 대신의 수 $N$이 주어진다. 둘째 줄에 첫째 대신부터 $N$번째 대신까지의 주급 $a_1$부터 $a_N$까지가 공백으로 구분되어 주어진다.

• $1 \le T \le 100$
• $1 \le N \le 100$
• $1 \le a_i \le 10000$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 가능한 이야기의 개수를 10007로 나눈 나머지이다.