이야기 하나 들려줄게 (Large)

공정왕 티론의 이야기를 하나 들려주겠다.

공정왕 티론에게는 장관이 $N$명 있었다. 장관은 서열 순으로 1번부터 $N$번까지 번호가 붙어 있고, $i$번 장관은 매주 금화 $s_i$개를 받았다.

어느 날 봉급 명세가 공개되었다. 그때부터 자기보다 서열이 낮은 장관 중에 자기보다 많이 받는 사람이 있으면 그 장관이 불만을 제기했고, 왕은 남아 있는 장관 중 정확히 한 명을 해임했다. 왕은 봉급을 조정하지도 않았고 서열을 바꾸지도 않았다. 해임되는 사람이 불만을 제기한 장관이거나 원인을 제공한 장관일 필요는 없다. 남아 있기만 하면 사건과 아무 상관이 없는 장관도 해임될 수 있다. 불만이 나올 수 있는 동안 해임이 이어졌고, 남은 장관의 봉급이 서열 순으로 비증가가 되는 순간 멈췄다. 남은 장관끼리의 서열 순서는 그대로 유지된다.

봉급이 $7, 4, 6, 6$일 때 가능한 이야기 하나는 이렇다. 2번 장관이 불만을 제기하자 왕은 1번 장관을 해임했고 $4, 6, 6$이 남았다. 2번 장관이 또 불만을 제기하자 왕은 그를 해임했고 $6, 6$이 남았다. $6, 6$에는 아무도 불만이 없으므로 해임이 멈췄다.

나는 봉급은 기억하지만 해임된 순서는 기억하지 못한다. 내가 들려줄 수 있는 이야기가 몇 가지인지 세어라. 해임된 장관의 순서열이 다르면 서로 다른 이야기다. 봉급이 같아도 원래 서열이 다르면 다른 장관이다. 처음부터 아무도 불만을 제기할 수 없으면 해임은 한 번도 일어나지 않고, 이야기는 빈 순서열 하나뿐이다.

답을 $10007$로 나눈 나머지를 출력한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄이다. 첫째 줄에 $N$이 주어지고, 둘째 줄에 1번 장관부터 $N$번 장관까지의 봉급 $s_1, s_2, \dots, s_N$이 공백으로 구분되어 주어진다.

제한

• $1 \le T \le 20$
• $1 \le N \le 8000$
• $1 \le s_i \le 10000$

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