부분배열 점수 구하기

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

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

Alice는 각 부분배열 $A[i, j]$의 점수 $Score(i, j)$를 다음 규칙으로 매긴다 ($1 \le i \le j \le 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에 따라 $0$이고, 규칙 2에 해당하는 부분배열은 없다. 길이가 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$가 주어졌을 때, $A$의 모든 부분배열 점수의 합을 구하라.

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

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

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