시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
40 초 (추가 시간 없음) 1024 MB (추가 메모리 없음) 9 9 9 100.000%

문제

We are cooking N pancakes in total. We cook one pancake with a 1 centimeter (cm) radius, one with a 2 cm radius, one with a 3 cm radius, ..., and one with an N cm radius, not necessarily in that order. After we cook the first pancake, we just lay it on a plate. After we cook each subsequent pancake, we lay it on top of the previously made pancake, with their centers coinciding. In this way, a pancake is visible from the top of the stack when we first add it. A pancake only becomes hidden if we later cook another pancake with a larger radius.

For example, say we cook 4 pancakes. We first cook the pancake with radius 3 cm, and it is visible. Then, we cook the pancake with radius 1 cm, lay it on top of the first one and both are visible. Third, we cook the pancake with radius 2 cm, and now that covers the previous pancake, but not the first one, so 2 pancakes remain visible in total. Finally, we cook the pancake with radius 4 cm which covers the other pancakes leaving only 1 visible pancake. The picture below illustrates the state of the stack after each pancake is cooked. Within each stack, the fully colored pancakes are visible and the semi-transparent pancakes are not visible.

Let Vi be the number of visible pancakes when the stack contains exactly i pancakes. In the example above, V1 = 1, V2 = 2, V3 = 2, and V4 = 1.

Given the list V1, V2, …, VN, how many of the N! possible cooking orders yield those values? Since the output can be a really big number, we only ask you to output the remainder of dividing the result by the prime 109+7 (1000000007).

입력

The first line of the input gives the number of test cases, T. T test cases follow, each described with two lines. The first line of a test case contains a single integer N, the number of pancakes we cook. The second line of a test case contains N integers V1, V2, ..., VN, representing the number of visible pancakes after we cook 1, 2, ..., N pancakes, respectively.

출력

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of cooking orders of N pancakes that yield the given numbers of visible pancakes after each step, modulo the prime 109+7 (1000000007).

제한

  • 1 ≤ T ≤ 100.
  • 1 ≤ Vi ≤ i, for all i.

Test Set 1 (10점)

  • 2 ≤ N ≤ 13.

Test Set 2 (21점)

  • 2 ≤ N ≤ 105.

예제 입력 1

3
4
1 2 2 1
3
1 1 2
3
1 1 3

예제 출력 1

Case #1: 1
Case #2: 2
Case #3: 0

Sample Case #1 is explained in the problem statement. The order 3, 1, 2, 4 is the only one that yields the given Vis.

In Sample Case #2, both the order 1, 3, 2 and the order 2, 3, 1 yield the intended Vis. The pictures below illustrate both options.

In Sample Case #3, only 11 pancake is visible after the second is made, so there is no way to have more than 22 visible pancakes by only adding a third.

예제 입력 2

1
24
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2

예제 출력 2

Case #1: 234141013

In the Sample Case for Test Set 2, there are 316234143225 cooking orders that yield the given Vis. Modulo 109+7, this value is 234141013.

채점 및 기타 정보

  • 예제는 채점하지 않는다.