사탕 골고루 먹기

Bob은 $n$가지 다른 종류의 사탕을 여럿 가지고 있다. 사탕은 $1$번부터 $n$번까지 번호가 붙어있고 $i$번 사탕은 $v\_i$개 갖고 있으며, $m = \sum\_{1 \le i \le n}{ v\_i}$ 를 사탕의 총 개수라 하자.

Bob은 오늘 자신이 가진 사탕 모두를 다 먹기로 했다. 단, 언제나 그렇듯 놀이를 하면서 먹기로 했다.

1. 우선 같은 종류의 사탕을 연속해서 먹지 않기로 했다. 아무래도 골고루 먹는 편이 더 맛있을 것 같기 때문이다.
2. 만약 위 조건을 만족하며 사탕을 먹을 수 있는 방법이 여럿 있다면, 사전순으로 가장 앞서는 방법으로 사탕을 먹기로 했다. 총 $m$개의 사탕을 먹는 방법은 길이가 $m$인 정수 배열로 표현 가능하며, 이 때 각 원소의 값은 사탕의 번호를 나타낸다. 이를테면 두 가지 방법 $X$와 $Y$가 있을 때, 편의상 $X$와 $Y$가 상기한대로 길이 $m$인 정수 배열이라 하자. $X$와 $Y$의 원소가 처음으로 다른 지점을 $k$라 하면 (즉, $1 ≤ i < k$에 대해서는 $X\[i] = Y\[i]$ 이지만 $X\[k] \ne Y\[k]$ 인 경우), $X\[k] < Y\[k]$ 이면 방법 $X$가 방법 $Y$보다 사전순으로 앞서고 $X\[k] > Y\[k]$ 이면 $Y$가 $X$보다 앞선다. 이 때, 두 정수 $X\[k]$ 와 $Y\[k]$는 대소비교를 하기에 예를 들어, $X\[k] = 10$ 이고 $Y\[k] = 5$인 경우 $X\[k] > Y\[k]$ 이다.

예를 들어 $n = 2$, $v = \[2, 2]$라 하자. 이 때, $1$번 조건을 만족하며 사탕을 모두 먹는 방법은 총 $2$가지가 있다.

• 방법 $1$: $\[1, 2, 1, 2]$
• 방법 $2$: $\[2, 1, 2, 1]$

이 두 가지 방법 중 방법 $1$이 사전순으로 앞선다.

다른 예로, $n = 3$, $v = \[2, 1, 4]$라 하자. 이 때, $1$번 조건을 만족하며 사탕을 모두 먹는 방법은 총 $3$가지가 있다 (사전순으로 정렬되어있다).

• 방법 $1$: $\[3, 1, 3, 1, 3, 2, 3]$
• 방법 $2$: $\[3, 1, 3, 2, 3, 1, 3]$
• 방법 $3$: $\[3, 2, 3, 1, 3, 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"을 출력한다 (따옴표 제외).