숨겨진 팬케이크

우리는 팬케이크를 총 N개 굽는다. 반지름이 1 cm인 팬케이크 하나, 반지름이 2 cm인 팬케이크 하나, 반지름이 3 cm인 팬케이크 하나, ..., 반지름이 N cm인 팬케이크 하나를 굽는데, 굽는 순서는 임의이다. 첫 번째 팬케이크를 구운 뒤에는 그냥 접시 위에 올린다. 그 뒤로 팬케이크를 구울 때마다 바로 전에 구운 팬케이크 위에 중심이 일치하도록 올린다. 이렇게 하면 새로 올린 팬케이크는 쌓인 더미의 위에서 볼 때 보인다. 팬케이크가 가려지는 것은 나중에 반지름이 더 큰 팬케이크를 구워 올릴 때뿐이다.

예를 들어 팬케이크 4개를 굽는다고 하자. 먼저 반지름이 3 cm인 팬케이크를 구우면 이것이 보인다. 다음으로 반지름이 1 cm인 팬케이크를 구워 첫 번째 팬케이크 위에 올리면 둘 다 보인다. 세 번째로 반지름이 2 cm인 팬케이크를 구우면 바로 전의 팬케이크는 가려지지만 첫 번째 팬케이크는 가려지지 않으므로, 보이는 팬케이크는 모두 2개이다. 마지막으로 반지름이 4 cm인 팬케이크를 구우면 나머지 팬케이크가 모두 가려져 보이는 팬케이크는 1개만 남는다. 아래 그림은 팬케이크를 하나씩 구운 뒤의 더미 상태를 나타낸다. 각 더미에서 색이 완전히 칠해진 팬케이크는 보이는 것이고, 반투명한 팬케이크는 보이지 않는 것이다.

더미에 팬케이크가 정확히 i개 있을 때 보이는 팬케이크의 수를 Vi라고 하자. 위 예에서 V1 = 1, V2 = 2, V3 = 2, V4 = 1이다.

V1, V2, …, VN이 주어졌을 때, N!가지의 가능한 굽는 순서 중 이 값들을 만족하는 순서는 몇 가지인가? 답이 매우 클 수 있으므로, 결과를 소수 109+7 (1000000007)로 나눈 나머지를 출력하시오.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 각각 두 줄로 주어진다. 테스트 케이스의 첫 줄에는 구울 팬케이크의 수 N이 주어진다. 둘째 줄에는 V1, V2, ..., VN이 주어지는데, 각각 팬케이크를 1, 2, ..., N개 구운 뒤 보이는 팬케이크의 수를 나타낸다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 각 단계 후 주어진 보이는 팬케이크 수를 만족하는 N개 팬케이크의 굽는 순서의 수를 소수 109+7 (1000000007)로 나눈 나머지이다.

• 1 ≤ T ≤ 100.
• 모든 i에 대해 1 ≤ Vi ≤ i.