사탕 골고루 먹기

Bob은 $n$가지 종류의 사탕을 여러 개 가지고 있다. 사탕은 1번부터 $n$번까지 번호가 붙어 있고, $i$번 사탕은 $v_i$개 있다. $m = \sum_{1 \le i \le n} v_i$를 사탕의 총 개수라 하자.

Bob은 오늘 가진 사탕을 모두 먹기로 했다. 단, 놀이를 하면서 먹는다.

1. 같은 종류의 사탕을 연속으로 먹지 않는다. 골고루 먹는 편이 더 맛있을 것 같기 때문이다.
2. 위 조건을 만족하며 사탕을 먹는 방법이 여럿이면, 사전순으로 가장 앞서는 방법을 택한다. 총 $m$개의 사탕을 먹는 방법은 길이가 $m$인 정수 배열로 나타낼 수 있으며, 각 원소의 값은 사탕의 번호이다. 두 방법 $X$와 $Y$가 있을 때, 처음으로 다른 위치를 $k$라 하자. 즉, $1 \le i < k$인 모든 $i$에 대해 $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을 출력한다 (따옴표 제외).