34986번 - 오량

문제

대신고에는 $N$명의 학생들이 있고, 각 학생은 자신의 노트를 하나씩 들고 온다. 처음에 $i$번째 학생은 $i$번 노트를 하나 가지고 있다.

대신고의 학생들은 점심시간에 다른 학생에게 오량을 하곤 한다. 오량이란 한 학생이 다른 학생의 모든 노트를 가져가는 것이다. 점심시간 동안 오량은 순서 제약 없이 여러 번 일어날 수 있으며, 오량이 일어나지 않을 수도 있다. 또한 두 개 이상의 오량이 동시에 일어나지 않음이 보장된다.

어느 날 대신이는 점심시간 이후 학생들이 오량을 했을 때 노트를 가지는 경우의 수가 얼마나 될지 궁금해졌다! 당신은 각 학생이 점심시간 이후 최종적으로 가지고 있는 노트의 개수가 주어졌을 때, 이 개수에 맞게 $N$개의 노트를 학생들이 가지게 되는 서로 다른 경우의 수를 구해야 한다. 서로 다른 경우란, 적어도 한 명이 가지고 있는 노트 번호의 집합이 다른 경우를 의미한다.

대신이를 도와 문제를 해결하는 코드를 작성해 주자.

입력

첫번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1 \leq T \leq 1,000円)$

각 테스트 케이스의 첫번째 줄에 대신고의 학생 수 $N$이 주어진다. $(2 \leq N \leq 2,000円)$

각 테스트 케이스의 두번째 줄에 각 학생이 점심시간 이후 가지고 있는 노트의 개수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(0 \leq A_i \leq N;$ $\sum_{i=1}^{N}A_i = N)$

출력

각 테스트 케이스에 대해 학생들이 노트를 가지는 경우의 수를 10ドル^9 + 7$로 나눈 나머지를 한 줄에 하나씩 순서대로 출력한다.

제한

노트