수학 인코더

Math 교수는 비밀 프로젝트를 진행하던 중, 수의 목록을 가장 효율적인 방식으로 하나의 수로 인코딩해야 하는 과제에 직면했다. 오랜 연구 끝에 Math 교수는 수들을 가장 잘 인코딩할 수 있는 3단계 과정을 찾아냈다.

• 첫 단계에서는 수의 목록에서 가능한 모든 공집합이 아닌 부분집합을 찾은 다음, 각 부분집합에서 가장 큰 수와 가장 작은 수의 차이(즉, 가장 큰 수에서 가장 작은 수를 뺀 값)를 구한다. 부분집합에 수가 하나만 있다면 그 수가 해당 부분집합에서 가장 큰 수인 동시에 가장 작은 수라는 점에 유의한다. 전체 집합 자체도 부분집합으로 간주한다.

• 그런 다음 모든 차이를 더해 최종 인코딩된 수를 구한다.

• 수가 클 수 있으므로, 그 수를 $10^{9}$ + 7 (1000000007)로 나눈 나머지를 출력한다.

교수는 아래에 예제와 그 설명을 공유했다. 수의 목록이 주어질 때, 교수가 최종 인코딩된 수를 계산하는 효율적인 함수를 만들도록 도와줄 수 있는가?

제한

1 ≤ T ≤ 25. 테스트 세트당 시간 제한: 20초. 메모리 제한: 1GB. 모든 i에 대해 1 ≤ $K_{i}$ ≤ 10000. 모든 i < N - 1에 대해 $K_{i}$ ≤ $K_{i+1}$.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 10.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 10000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 2개의 줄로 정의된다.

• 첫 줄에는 양수 N, 즉 목록에 있는 수의 개수가 주어지고

• 둘째 줄에는 비내림차순으로 정렬된 N개의 양의 정수 목록 $K_{i}$이 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 1부터 시작하는 테스트 케이스 번호이고, y은 최종 인코딩된 수이다.

출력값은 매우 큰 수일 수 있으므로, 결과를 소수 $10^{9}$ + 7 (1000000007)로 나눈 나머지만 출력한다.

예제 입력 설명

• 모든 부분집합을 찾고 가장 큰 수와 가장 작은 수의 차이를 구한다. $[3]$, 가장 큰 수-가장 작은 수 = 3 - 3 = 0. $[6]$, 가장 큰 수-가장 작은 수 = 6 - 6 = 0. $[7]$, 가장 큰 수-가장 작은 수 = 7 - 7 = 0. $[9]$, 가장 큰 수-가장 작은 수 = 9 - 9 = 0. $[3, 6]$, 가장 큰 수-가장 작은 수 = 6 - 3 = 3. $[3, 7]$, 가장 큰 수-가장 작은 수 = 7 - 3 = 4. $[3, 9]$, 가장 큰 수-가장 작은 수 = 9 - 3 = 6. $[6, 7]$, 가장 큰 수-가장 작은 수 = 7 - 6 = 1. $[6, 9]$, 가장 큰 수-가장 작은 수 = 9 - 6 = 3. $[7, 9]$, 가장 큰 수-가장 작은 수 = 9 - 7 = 2. $[3, 6, 7]$, 가장 큰 수-가장 작은 수 = 7 - 3 = 4. $[3, 6, 9]$, 가장 큰 수-가장 작은 수 = 9 - 3 = 6. $[3, 7, 9]$, 가장 큰 수-가장 작은 수 = 9 - 3 = 6. $[6, 7, 9]$, 가장 큰 수-가장 작은 수 = 9 - 6 = 3. $[3, 6, 7, 9]$, 가장 큰 수-가장 작은 수 = 9 - 3 = 6.

• 이전 단계에서 계산한 차이들의 합을 구한다. 3+4+6+1+3+2+4+6+6+3+6 = 44.

• 답을 $10^{9}$ + 7 (1000000007)로 나눈 나머지를 구한다. 44 % 1000000007 = 44