문제

대신고에는 명의 학생들이 있고, 각 학생은 자신의 노트를 하나씩 들고 온다. 처음에 번째 학생은 번 노트를 하나 가지고 있다. 대신고의 학생들은 점심시간 때에 다른 학생에게 오량을 하곤 한다. 오량이란 한 학생이 다른 학생의 모든 노트를 가져가는 것이다.

점심시간 동안 오량은 아무런 순서 제약 없이, 몇 번이든 일어날 수 있다. 혹은 오량이 단 한번도 일어나지 않을 수도 있다. 두 개 이상의 오량이 동시에 일어나지 않는다 가정한다.

어느 날 대신이는 점심시간 이후 학생들이 오량을 했을 때 노트를 나누어 가지는 경우의 수가 얼마나 될지 궁금해졌다! 당신은 각 학생이 점심시간 이후 최종적으로 가지고 있는 노트의 개수가 주어졌을 때, 이 개수에 맞게 개의 노트들을 학생들이 가지게 되는 서로 다른 방법의 경우의 수를 구해야 한다. '서로 다른 경우'란, 적어도 한 명 이상의 학생이 가지고 있는 노트의 집합이 다른 경우를 의미한다. 대신이를 도와 문제를 해결하는 코드를 작성해 주자.

입력

첫번째 줄에 테스트 케이스의 개수 가 주어진다.

각 테스트 케이스의 첫번째 줄에는 대신고의 학생의 수 이 주어진다.()

각 테스트 케이스의 두번째 줄에는 각 학생이 점심시간 이후 가지고 있는 노트의 개수 이 공백으로 구분되어 주어진다.(; )

출력

각 테스트 케이스에 대해 한 줄에 하나씩 학생들이 노트를 가지는 경우의 수를 로 나눈 나머지를 출력한다.

노트

예제 1의 첫 번째 테스트 케이스의 경우, 각 학생이 최종적으로 가질 수 있는 노트의 집합을 나열했을때, 아래의 3가지의 경우가 있다.

{1}, {}, {2,3}, {2}, {}, {1,3}, {3}, {}, {1,2}

예제 1의 두 번째 테스트 케이스의 경우, 1번 학생이 1번 노트와 2번 노트 둘 다 가져가는 경우만 있으므로 1가지의 경우가 있다.