사탕 놀이

수학 선생님 Albert는 사탕을 좋아하는 반 아이들을 위해 재미있는 놀이를 고안했다. 아이들은 아직 어려서 자연수만 알고 있고, 각 아이마다 알고 있는 자연수의 범위가 다르다. 편의상 아이들은 1부터 n까지 번호가 붙어있다고 하고, i번째 아이는 1 이상 x[i] 이하의 자연수를 알고 있다고 하자.

놀이는 아래 규칙에 따라 진행된다.

1. 각 턴이 시작되면 아이들은 각자 알고 있는 자연수 중 아무 수나 골라서 종이에 적는다.
2. 모두 원하는 수를 적었으면 Albert 선생님이 n장의 종이를 모은다.
3. Albert 선생님은 이 수들을 비내림차순으로 정렬하여 길이 n인 수열을 만든다 (수열 A라고 하자).
4. 만약 수열 A가 이전 턴에 한 번이라도 만들어진 적이 있으면 수열은 버려지고 게임은 계속 진행된다.
5. 만약 수열 A가 이전 턴에 만들어진 적이 없다면 Albert 선생님이 아이들에게 사탕을 하나씩 나누어주고 게임이 계속 진행된다.
6. 모든 가능한 (정렬된) 수열이 만들어진 후에 게임이 완전히 끝나게 된다.

모든 아이들이 자연수의 일부만 알고 있기 때문에 이 게임은 언젠가 끝나게 된다. 하지만 Albert 선생님은 미리 사탕을 준비해야 하므로 최대 몇 개를 나눠줘야 할지 알고 싶다. 학생 수 n과 각 학생이 알고 있는 자연수의 범위가 주어졌을 때, Albert 선생님이 나눠줘야 하는 사탕의 최대 수를 구해서 선생님을 도와주도록 하자. 다만 이 수는 매우 클 수 있으므로 1,000,000,007로 나눈 나머지를 구해주기로 했다.

예를 들어 Albert 선생님의 반에 두 명의 아이가 있고 이 두 아이가 각자 1 이상 3 이하의 자연수만 안다고 해보자. 이 경우 비내림차순으로 정렬된 수열은 모두 여섯 가지다: {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3}. 각 수열이 처음 만들어지는 턴에 Albert 선생님이 사탕 두 개를 나누어주어야 하므로 총 12개의 사탕을 미리 준비해놔야 한다.

첫 줄에 테스트 케이스의 수 T가 주어진다 (1 <= T <= 10).

각 테스트 케이스는 두 줄에 걸쳐서 주어진다. 첫 줄에 학생 수 n이 주어지고 (1 <= n <= 200) 둘째 줄에 배열 x[]를 표현하는 n개의 자연수가 공백으로 구분되어 주어진다. 각 i에 대해 1 <= x[i] <= 200을 만족한다.

각 테스트 케이스에 대해 Albert 선생님이 준비해야 하는 사탕의 최대 수를 1,000,000,007로 나눈 나머지를 출력한다.

• 케이스 1: 아이 한 명이 1 이상 3 이하의 수를 알기 때문에 정답은 3이다. 정렬된 수열은 {1}, {2}, {3} 이렇게 세 가지 존재한다.
• 케이스 2: 문제에서 예시로 사용되었다.
• 케이스 3: 이 경우 정렬된 수열은 모두 다섯 개다: {1, 1, 1}, {1, 1, 2}, {1, 1, 3}, {1, 2, 2}, {1, 2, 3}. 학생이 세 명 있기 때문에 이 수열 각각이 처음으로 만들어지는 턴에 Albert는 사탕을 3개씩 나눠주어야 하므로 총 15개의 사탕을 준비해야 한다.
• 케이스 4: 답이 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력해야 함에 유의하자. 이 경우 정렬된 수열은 총 1,604,563,870가지이고 여섯 명의 아이가 있으므로 사탕은 총 9,627,383,220개 필요하다. 9,627,383,220을 1,000,000,007로 나눈 나머지는 627,383,157이다.