킥스타트 알람

Shil은 매일 아침 잠에서 깨는 것을 매우 힘들어해서, 하루를 힘차게 시작하기 위해 강력한 알람 시계를 사기로 한다. 이 알람을 Kickstart Alarm이라고 한다. 이 시계에는 강력한 모닝콜 K개가 미리 설정되어 있다. 사용자는 잠자리에 들기 전에 $A_{1}$, $A_{2}$, ..., $A_{N}$ 값으로 구성된 Parameter Array을 시계에 입력한다. 아침이 되면 시계는 K번 울리며, i번째 모닝콜의 세기는 $POWER_{i}$이다.

$POWER_{i}$을 계산하기 위해, 알람은 Parameter Array의 모든 연속 부분 배열을 생성하고 모든 연속 부분 배열의 i번째 지수 세기의 합을 계산한다. 부분 배열 $A_{j}$, $A_{j+1}$, ..., $A_{k}$의 i번째 지수 세기는 $A_{j}$ × $1^{i}$ + $A_{j+1}$ × $2^{i}$ + $A_{j+2}$ × $3^{i}$ + ... + $A_{k}$ × (k-j+1)^{i}로 정의한다. 따라서 $POWER_{i}$은 Parameter Array의 모든 연속 부분 배열의 i번째 지수 세기를 합한 값이다.

예를 들어, i = 2이고 $A = [1, 4, 2]$라면 A의 i번째 지수 세기는 다음과 같이 계산한다:

• $[1]$의 2번째 지수 세기 = 1 × $1^{2}$ = 1

• $[4]$의 2번째 지수 세기 = 4 × $1^{2}$ = 4

• $[2]$의 2번째 지수 세기 = 2 × $1^{2}$ = 2

• $[1, 4]$의 2번째 지수 세기 = 1 × $1^{2}$ + 4 × $2^{2}$ = 17

• $[4, 2]$의 2번째 지수 세기 = 4 × $1^{2}$ + 2 × $2^{2}$ = 12

• $[1, 4, 2]$의 2번째 지수 세기 = 1 × $1^{2}$ + 4 × $2^{2}$ + 2 × $3^{2}$ = 35

따라서 총합은 71이다.

오늘 밤 Shil은 Kickstart Alarm을 처음 사용한다. 그래서 그는 아침에 알람이 낼지도 모르는 소리를 상당히 걱정하고 있다. 이웃들이 깨어날 수도 있고, 더 나쁘게는 지구 전체가 깨어날 수도 있다! 하지만 각 모닝콜의 세기를 계산하는 것은 그에게 상당히 어렵다. K와 Parameter Array $A_{1}$, $A_{2}$, ..., $A_{N}$가 주어질 때, 각 모닝콜의 세기의 합인 $POWER_{1}$ + $POWER_{2}$ + ... + $POWER_{K}$을 계산하도록 그를 도와줄 수 있는가?

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 90초. 메모리 제한: 1 GB. 1 ≤ $x_{1}$ ≤ $10^{5}$. 1 ≤ $y_{1}$ ≤ $10^{5}$ 1 ≤ C ≤ $10^{5}$. 1 ≤ D ≤ $10^{5}$. 1 ≤ $E_{1}$ ≤ $10^{5}$. 1 ≤ $E_{2}$ ≤ $10^{5}$. 1 ≤ F ≤ $10^{5}$.

소규모 데이터셋 (테스트 세트 1 - 공개)

1 ≤ N ≤ 100. 1 ≤ K ≤ 20.

대규모 데이터셋 (테스트 세트 2 - 비공개)

1 ≤ N ≤ $10^{6}$. 1 ≤ K ≤ $10^{4}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 아홉 개의 정수 N, K, $x_{1}$, $y_{1}$, C, D, $E_{1}$, $E_{2}$, F가 있는 한 줄로 구성된다. N은 배열 A의 길이이고, K는 모닝콜의 수이다. 나머지 값들은 다음과 같이 배열 A의 원소를 생성하는 데 사용해야 하는 매개변수이다.

아래 점화식을 사용하여 i = 2부터 N까지의 $x_{i}$와 $y_{i}$을 생성한다:

• $x_{i}$ = ( C × $x_{i-1}$ + D × $y_{i-1}$ + $E_{1}$ )를 F로 나눈 나머지.

• $y_{i}$ = ( D × $x_{i-1}$ + C × $y_{i-1}$ + $E_{2}$ )를 F로 나눈 나머지.

모든 i = 1부터 N까지에 대해 $A_{i}$ = ( $x_{i}$ + $y_{i}$ )를 F로 나눈 나머지로 정의한다.

각 테스트 케이스마다 Case #x: POWER을 포함하는 한 줄을 출력한다. 여기서 x은 1부터 시작하는 테스트 케이스 번호이고, POWER은 i = 1부터 K까지의 $POWER_{i}$을 합한 값이다. POWER은 매우 클 수 있으므로, 이를 1000000007 ($10^{9}$ + 7)로 나눈 나머지를 출력한다.

예제 케이스 #1에서 Parameter Array은 $[3, 2]$이다. 모든 연속 부분 배열은 $[3]$, $[2]$, $[3, 2]$이다.

i = 1의 경우:

• $[3]$의 1번째 지수 세기 = 3 × $1^{1}$ = $[2]$의 3

• 1번째 지수 세기 = 2 × $1^{1}$ = $[3, 2]$의 2

• 1번째 지수 세기 = 3 + 2 × $2^{1}$ = 7

따라서 $POWER_{1}$은 12이다.

i = 2의 경우:

• $[3]$의 2번째 지수 세기 = 3 × $1^{2}$ = $[2]$의 3

• 2번째 지수 세기 = 2 × $1^{2}$ = $[3, 2]$의 2

• 2번째 지수 세기 = 3 + 2 × $2^{2}$ = 11

따라서 $POWER_{2}$은 16이다.

i = 3의 경우:

• $[3]$의 3번째 지수 세기 = 3 × $1^{3}$ = $[2]$의 3

• 3번째 지수 세기 = 2 × $1^{3}$ = $[3, 2]$의 2

• 3번째 지수 세기 = 3 + 2 × $2^{3}$ = 19

따라서 $POWER_{3}$은 24이다.