숨겨진 팬케이크

우리는 총 $\mathbf{N}$개의 팬케이크를 굽는다. 반지름이 $1$센티미터(cm)인 팬케이크 하나, 반지름이 $2$cm인 팬케이크 하나, 반지름이 $3$cm인 팬케이크 하나, ..., 반지름이 $\mathbf{N}$cm인 팬케이크 하나를 굽되, 반드시 그 순서대로 굽지는 않는다. 첫 번째 팬케이크를 구운 뒤에는 그저 접시 위에 놓는다. 이후의 각 팬케이크를 구운 뒤에는 두 팬케이크의 중심이 일치하도록 이전에 만든 팬케이크 위에 놓는다. 이 방식에서는 팬케이크를 처음 추가했을 때 그 팬케이크가 쌓인 더미의 위쪽에서 보인다. 팬케이크는 나중에 반지름이 더 큰 다른 팬케이크를 구운 경우에만 숨겨진다.

예를 들어 $4$개의 팬케이크를 굽는다고 하자. 먼저 반지름이 $3$cm인 팬케이크를 구우면 이 팬케이크가 보인다. 그다음 반지름이 $1$cm인 팬케이크를 구워 첫 번째 팬케이크 위에 놓으면 둘 다 보인다. 세 번째로 반지름이 $2$cm인 팬케이크를 구우면, 이제 이 팬케이크가 바로 전에 구운 팬케이크는 덮지만 첫 번째 팬케이크는 덮지 않으므로 총 $2$개의 팬케이크가 계속 보인다. 마지막으로 반지름이 $4$cm인 팬케이크를 구우면 다른 팬케이크들을 덮어 $1$개의 팬케이크만 보이게 된다. 아래 그림은 각 팬케이크를 구운 뒤 쌓인 더미의 상태를 보여 준다. 각 더미에서 완전히 색칠된 팬케이크는 보이고 반투명한 팬케이크는 보이지 않는다.

더미에 정확히 $i$개의 팬케이크가 있을 때 보이는 팬케이크의 수를 $\mathbf{V_i}$라고 하자. 위 예에서 $\mathbf{V_1} = 1$, $\mathbf{V_2} = 2$, $\mathbf{V_3} = 2$, $\mathbf{V_4} = 1$이다.

목록 $\mathbf{V_1}, \mathbf{V_2}, \dots, \mathbf{V_N}$가 주어질 때, 가능한 $\mathbf{N}!$개의 조리 순서 중 해당 값들을 만드는 순서는 몇 개인가? 출력값이 매우 큰 수일 수 있으므로, 결과를 소수 $10^9+7$ ($1000000007$)로 나눈 나머지만 출력한다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$에 대해 $1 \le \mathbf{V_i} \le i$.

테스트 세트 1 (Visible Verdict)

시간 제한: 30초. $2 \le \mathbf{N} \le 13$.

테스트 세트 2 (Hidden Verdict)

시간 제한: 40초. $2 \le \mathbf{N} \le 10^5$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 각각 두 줄로 설명되는 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 굽는 팬케이크의 수인 정수 $\mathbf{N}$ 하나가 주어진다. 테스트 케이스의 두 번째 줄에는 각각 $1$, $2$, ..., $\mathbf{N}$개의 팬케이크를 구운 뒤 보이는 팬케이크의 수를 나타내는 $\mathbf{N}$개의 정수 $\mathbf{V_1}$, $\mathbf{V_2}$, ..., $\mathbf{V_N}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 각 단계가 끝난 뒤 주어진 수만큼의 팬케이크가 보이게 하는 $\mathbf{N}$개 팬케이크의 조리 순서 수를 소수 $10^9+7$ ($1000000007$)로 나눈 나머지이다.

예제 케이스 #1은 문제 설명에 설명되어 있다. 주어진 $\mathbf{V_i}$들을 만드는 순서는 $3, 1, 2, 4$뿐이다.

예제 케이스 #2에서는 순서 $1, 3, 2$와 순서 $2, 3, 1$가 모두 의도한 $\mathbf{V_i}$들을 만든다. 아래 그림들은 두 선택지를 모두 보여 준다.

예제 케이스 #3에서는 두 번째 팬케이크를 만든 뒤 $1$개의 팬케이크만 보이므로, 세 번째 팬케이크 하나를 추가하는 것만으로 보이는 팬케이크를 $2$개보다 많게 만들 방법은 없다.

추가 예제 - 테스트 세트 2

테스트 세트 2의 예제 케이스에서는 주어진 $\mathbf{V_i}$들을 만드는 조리 순서가 $316234143225$개 있다. 이 값을 $10^9+7$로 나눈 나머지는 $234141013$이다.