| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (하단 참고) | 512 MB | 81 | 15 | 9 | 25.714% |
Bob은 $n$가지 다른 종류의 사탕을 여럿 가지고 있다. 사탕은 1ドル$번부터 $n$번까지 번호가 붙어있고 $i$번 사탕은 $v_i$개 갖고 있으며, $m = \sum_{1 \le i \le n}{ v_i}$ 를 사탕의 총 개수라 하자.
Bob은 오늘 자신이 가진 사탕 모두를 다 먹기로 했다. 단, 언제나 그렇듯 놀이를 하면서 먹기로 했다.
예를 들어 $n = 2,ドル $v = [2, 2]$라 하자. 이 때, 1ドル$번 조건을 만족하며 사탕을 모두 먹는 방법은 총 2ドル$가지가 있다.
이 두 가지 방법 중 방법 1ドル$이 사전순으로 앞선다.
다른 예로, $n = 3,ドル $v = [2, 1, 4]$라 하자. 이 때, 1ドル$번 조건을 만족하며 사탕을 모두 먹는 방법은 총 3ドル$가지가 있다 (사전순으로 정렬되어있다).
입력으로 $n$과 $v_i$ 값들이 주어졌을 때, Bob이 위 조건을 만족하며 모든 사탕을 다 먹을 수 있는지 알아보자. 만약 가능하다면, 그 중 사전순으로 가장 앞서는 방법을 나타내는 길이 $m$인 정수 배열을 $Z$라 했을 때, $ \sum_{1 \le i \le m} {(i \cdot Z[i])} $ 값을 구해보자 단, 이 값이 너무 커질 수 있으므로 987ドル,654円,323円$로 나눈 나머지를 출력한다.
첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 두 줄에 걸쳐 주어진다.
첫째 줄에 사탕의 종류 $n$이 주어지며 둘째 줄에 $n$개의 정수가 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답을 각 줄에 출력한다.
만약 조건을 만족하며 사탕을 다 먹을 수 없는 경우 "IMPOSSIBLE"을 출력한다 (따옴표 제외).
8 2 2 2 3 2 1 4 3 2 6 3 3 8 6 4 10 1 1 1 1 1 1 1 1 1 1 4 2 1 1 3 2 6 4 3 1 1 9
16 66 150 338 385 87 IMPOSSIBLE IMPOSSIBLE