부분배열 점수 구하기

Alice는 정수 배열을 이용한 놀이를 즐겨한다.

길이 $n$인 정수 배열 $A$가 있을 때 $i$번째 원소를 $A\[i]$라 하자 ($i = 1, 2, \dots, n$). 이때 $A$의 부분배열 $A\[i, j]$는 $i$번째 원소부터 $j$번째 원소까지를 포함한 길이 $(j - i + 1)$인 배열로 정의한다 ($1 ≤ i ≤ j ≤ n$). 예를 들어 $A = \[1, 3, 5, 7]$이라면 $A\[1, 2]$은 $\[1, 3]$이고 $A\[2, 4]$은 $\[3, 5, 7]$이 된다. 참고로 $A$의 부분 배열은 총 $n \times (n+1) / 2$개 존재한다.

각각의 부분배열 $A\[i, j]$에 대하여 Alice는 아래와 같은 방법으로 점수를 매기기로 했다. 편의상 $A\[i, j]$의 점수를 $Score(i, j)$라 하자. ($1 ≤ i ≤ j ≤ n$)

• [규칙 1] 만약 $i = j$ 라면 $Score(i, j) := 0$이다.
• [규칙 2] 만약 $i < j$ 이고 $A\[i, j]$의 원소 중 중복된 값이 있다면 $Score(i, j) := 0$ 이다.
• [규칙 3] 만약 $i < j$ 이고 $A\[i, j]$의 원소 중 중복된 값이 없다면 $Score(i, j) := i^{(j - i + 1)} + j^{(j - i + 1)}$ 이다.

예를 들어 $A = \[1, 1, 2]$ 인 경우를 살펴보자.

• 규칙 1에 따라 $Score(1, 1) = Score(2, 2) = Score(3, 3) = 0$ 이다.
• 규칙 2에 따라 $Score(1, 2) = Score(1, 3) = 0$ 이다. 두 경우 모두 부분 배열에 $1$이 한 번 이상 포함되기 때문이다.
• 규칙 3에 따라 $Score(2, 3) = 2^2 + 3^2 = 13$이다.

다른 예로, $A = \[1, 3, 5, 7]$ 인 경우를 살펴보자.

• 규칙 1에 따라 $Score(1, 1) = Score(2, 2) = Score(3, 3) = Score(4, 4) = 0$이다.

• 규칙 2에 해당하는 부분 배열은 없다.

• 규칙 3에 따라 길이 $2$ 이상의 모든 부분 배열의 점수를 구하면 아래와 같다:

  • $Score(1, 2) = 1^2 + 2^2 = 5$
  • $Score(2, 3) = 2^2 + 3^2 = 13$
  • $Score(3, 4) = 3^2 + 4^2 = 25$
  • $Score(1, 3) = 1^3 + 3^3 = 28$
  • $Score(2, 4) = 2^3 + 4^3 = 72$
  • $Score(1, 4) = 1^4 + 4^4 = 257$

정수 배열 $A$가 주어졌을 때, Alice를 도와 $A$의 부분배열 점수 총합을 구해보자.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 배열의 길이 $n$이 주어지고 둘째 줄에는 $A$의 원소인 $n$개의 정수가 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답을 각 줄에 출력한다. 단, 답이 매우 커질 수 있으므로 정답을 $10^9+7$로 나눈 나머지를 출력한다.