Description

故事是这样的……

很久很久以前，仁慈的泰隆国王有四位大臣。第一位大臣（国王的首席顾问）每周工资为 7 枚金币。第二位大臣每周工资为 4 枚金币。第三和第四位大臣每周各得 6 枚金币。不幸的是，泰隆有一天不小心把《大臣薪酬名单》落在了复印机上，结果这份名单被登上了王国时报的头版。于是第二位大臣请求觐见国王，对自己工资竟然低于级别更低的第三位大臣感到很不满。

仁慈的泰隆国王觉得别无他法，只能解雇第三位大臣。毕竟，在国王看来，降低第三位大臣工资、提高第二位大臣工资，或者更改职位头衔，这些做法都不公平。我们又怎敢质疑泰隆国王的决定呢？当然，解雇第三位大臣并没有解决问题。第二位大臣仍然抱怨，因为他的工资依然低于第四位大臣。于是泰隆国王也解雇了第四位大臣。此时，剩下的两位大臣都没有再抱怨，大家从此过上了幸福的生活。

……等一下。我好像讲错了。抱歉，我的记忆不如从前了。让我再想想……没错，仁慈的泰隆国王，四位大臣，工资分别为 7、4、6 和 6。啊，对了，结尾其实是这样的……

第二位大臣抱怨不公时，泰隆国王解雇了第一位大臣。有人可能会觉得这有点过分，毕竟第一位大臣其实完全没参与这场纠纷，但我们不该质疑泰隆国王的决定。显然，第二位大臣还是不满意，于是国王干脆把他也解雇了。剩下的两位大臣，工资都不低于后面的大臣，所以没人再抱怨了。大家从此过上了幸福的生活。

这样讲好多了……是吧？现在我又不确定了。我只记得那时有 $N$ 位大臣，而且我清楚地记得他们的工资。我还记得，每当某位大臣的工资低于后面某位大臣时，就会有人抱怨，然后会解雇一位大臣；但被解雇的可以是任何一位，无论他是否与问题有关。大臣们会不断被解雇，直到没有人再抱怨，也就是所有工资都是不递增的。这时，解雇才会停止。但我不记得大臣们被解雇的顺序了。

你能帮我补全这个故事吗？或者，至少请你算一算，我一共能讲出多少种不同的故事。若解雇大臣的顺序不同，则认为是不同的故事。

Input Format

第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据包含两行。第一行为一个整数 $N$，第二行为 $N$ 个用空格隔开的整数，表示这 $N$ 位大臣的工资，按从第一位到第 $N$ 位的顺序给出。

Output Format

对于每个测试用例，输出一行 "Case #$x$: $y$"，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为我能讲出的故事数量，对 $10007$ 取模。

3
4
7 4 6 6
8
90 80 70 60 50 50 40 30
2
7 8

Case #1: 14
Case #2: 1
Case #3: 2

Hint

限制条件

• 每位大臣的工资均为正，且不超过 $10000$。

小数据集（14 分，测试集 1 - 可见）

• 时间限制：60 10 秒
• $1 \leq T \leq 100$
• $1 \leq N \leq 100$

大数据集（50 分，测试集 2 - 隐藏）

• 时间限制：120 20 秒
• $1 \leq T \leq 20$
• 80% 的测试点满足 $1 \leq N \leq 2000$
• 所有测试点满足 $1 \leq N \leq 8000$

翻译由 ChatGPT-4.1 完成。