시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 125 | 83 | 62 | 73.810% |
수학 선생님 Albert는 사탕을 좋아하는 반 아이들을 위해 재미있는 놀이를 고안했다. 아이들은 아직 어려서 자연수만 알고 있고, 각 아이마다 알고 있는 자연수의 범위가 다르다. 편의상 아이들은 1부터 n까지 번호가 붙어있다고 하고, i번째 아이는 1이상 x[i] 이하의 자연수를 알고 있다고 가정하자.
놀이는 아래와 같은 규칙에 따라 진행된다.
모든 아이들이 자연수의 일부만 알고 있기 때문에 이 게임은 언젠가 끝나게 된다. 하지만 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로 나눈 나머지를 출력한다.
4 1 3 2 3 3 3 1 2 3 6 95 96 97 98 99 100
3 12 15 627383157