#138 · let-me-tell-you-a-story-f5be86

让我给你讲个故事

Not startedHard
Time10.0 s
Memory1,024 MB
Submissions0
Acceptance0.0%
0%100%

Statement

故事是这样的...

*很久很久以前,King Tyrone the Fair 有 4 位大臣。第一位大臣(国王的首席顾问)每周的薪水是 7 枚金币。第二位大臣每周的薪水是 4 枚金币。第三位和第四位大臣每周的薪水各是 6 枚金币。不幸的是,有一天 Tyrone 不小心把 Ministerial Compensation List 忘在了复印机里,这份 List 最后出现在了 Kingdom Times 报纸的头版上。此时,第二位大臣因为自己的薪水低于排名更低的第三位大臣而感到不满,请求与国王谈话。*

*公平的 King Tyrone 认为除了解雇第三位大臣之外别无他法。毕竟,在国王看来,降低第三位大臣的薪水、提高第二位大臣的薪水,或者更改职位头衔,都是不公平的解决办法。我们又何德何能去质疑 King Tyrone 呢?当然,解雇第三位大臣并没有解决问题。第二位大臣继续抱怨,因为他的薪水仍然低于第四位大臣。于是 King Tyrone 也解雇了第四位大臣。此时,剩下的两位大臣都不再抱怨,从此大家都过上了幸福快乐的生活。*

...等等。我搞错了。对不起。我的记忆已经不如从前了。请稍等……对了。King Tyrone the Fair。四位大臣。薪水分别是 7、4、6 和 6。啊,是的。结局是这样的……

*当第二位大臣抱怨不公平时,King Tyrone 解雇了第一位大臣。有些人可能会说这有点严厉,因为第一位大臣完全没有牵涉其中,但我们不应该质疑 King Tyrone。显然,第二位大臣仍然抱怨,所以 King Tyrone 干脆解雇了他。在剩下的两位大臣中,每个人得到的薪水都不低于任何排在他后面的大臣,所以他们都没有抱怨。从此大家都过上了幸福快乐的生活。*

好多了...我想。也许吧?现在我又不确定了。我确定有 N 位大臣,而且我清楚地记得他们的薪水。我还知道,每当一位大臣的薪水低于排在他后面的大臣的薪水时,就会有人抱怨,并且 *某位大臣* 会被解雇;但这可能是 *任意一位大臣*,无论这位大臣是否与问题有任何关系。大臣们会继续被解雇,直到因为所有薪水都是非递增的而没有人抱怨。到那时,解雇就停止了。但我不记得大臣们被解雇的顺序。

你能帮我修正我的故事吗?或者至少请告诉我,我可能讲了多少个不同的故事。如果两个故事中被解雇大臣的序列不相同,那么这两个故事就是不同的。

Input

输入的第一行给出测试用例数 T。接下来有 T 个测试用例。每个测试用例由两行组成。第一行包含一个整数 N,第二行包含 N 个以空格分隔的整数,按从第一位大臣到第 N 位大臣的顺序表示大臣们的薪水。

### 数据范围

- 每个薪水均为正且至多为 10000。
- 1 ≤ T ≤ 100。
- 1 ≤ N ≤ 100。
- 1 ≤ T ≤ 20。
- 对于 80% 的测试用例,1 ≤ N ≤ 2000。
- 对于所有测试用例,1 ≤ N ≤ 8000。

Output

对于每个测试用例,按测试用例顺序逐个输出答案,输出一行,包含 "y",其中 y 是我能给你讲的故事数量,对 10007 取模。

Examples

Example 1

Input

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

Output

14
1
2

Constraints

  • Time limit: 10000 ms
  • Memory limit: 1048576 KB
  • Tag: dynamic-programming
  • Tag: math

Loading language catalog...