Let Me Tell You a Story (Small)

An old storyteller keeps changing his mind about how one story ended.

King Tyrone had four ministers. From the highest rank down, their weekly pay was 7, 4, 6 and 6 gold pieces. When the pay list reached the newspaper, the second minister protested that a minister of lower rank was paid more than he was. The king would not touch a salary and would not touch a rank, so he fired someone instead. In one version he fired the third minister, then the fourth. In another version he fired the first minister, who had nothing to do with the protest, and then fired the second minister because the protest was still standing. Both versions end the same way. The pay of the ministers who are left never rises as you read down the ranks, nobody protests, and the firings stop.

The storyteller no longer remembers the order of the firings, only the rules. There were $N$ ministers, numbered $1$ to $N$ from the highest rank to the lowest, and minister $i$ was paid $a_i$ gold pieces per week. A protest happens whenever two serving ministers $i < j$ satisfy $a_i < a_j$. While at least one protest stands, the king fires exactly one of the ministers still serving. He may fire any of them, including a minister who takes no part in any protest. The ministers who remain keep their relative ranks. Once the pay of the serving ministers never rises as you read down the ranks, nobody protests and nobody else is fired.

A story is the sequence of fired ministers written in the order they were fired. Two stories are different when those sequences are different. If nobody protests at the start, nobody is fired and the empty sequence is the only story. Count the stories the storyteller could tell, modulo 10007.

The first line contains the number of test cases $T$. Each test case takes two lines. The first line contains the number of ministers $N$. The second line contains $N$ space separated integers $a_1$ to $a_N$, the weekly pay of the first minister through the $N$th minister.

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

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