Let Me Tell You a Story (Large)

Let me tell you a story about King Tyrone the Fair.

King Tyrone the Fair had $N$ ministers, ranked from the first minister down to the $N$-th minister. The $i$-th minister was paid $s_i$ gold pieces per week.

One day the salary list became public. From then on, whenever a minister was paid less than some minister ranked below him, that minister complained, and the king fired exactly one of the ministers still in office. The king never changed a salary and never changed a rank. The minister he fired did not have to be the one who complained or the one who caused the complaint. It could be any minister still in office, even one with nothing to do with the problem. The ministers who stay keep their relative ranks. Firings went on as long as a complaint was possible, and stopped the moment the salaries of the remaining ministers were non-increasing from the highest rank to the lowest.

One story for the salaries $7, 4, 6, 6$ goes like this. The second minister complained, so the king fired the first minister and $4, 6, 6$ remained. The second minister complained again, so the king fired him and $6, 6$ remained. Nobody complains about $6, 6$, so the firings stopped.

I remember the salaries, but not the order in which the ministers were fired. Count how many stories I could tell. Two stories are different if the sequences of fired ministers are different. Ministers are told apart by their original rank, even when their salaries are equal. If nobody can complain at the start, no minister is ever fired and the only story is the empty sequence.

Print the count modulo $10007$.

The first line contains the number of test cases $T$. Each test case takes two lines. The first line contains $N$, and the second line contains $N$ space separated integers $s_1, s_2, \dots, s_N$, the salaries from the first minister to the $N$-th minister.

Constraints

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

For each test case, print one line of the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of stories modulo $10007$.