Kickstart Alarm

Shil은 아침에 일어나는 일이 매일 매우 힘들어서, 하루를 Kickstart할 강력한 알람 시계를 사기로 한다. 이 알람은 Kickstart Alarm이라 불리며, K개의 강력한 기상 호출이 미리 설정되어 있다. 잠들기 전에 사용자는 A1, A2, ..., AN 값으로 이루어진 매개변수 배열(Parameter Array)을 시계에 입력한다. 아침이 되면 시계는 K번 울리며, i번째 기상 호출의 세기는 POWERi이다.

POWERi를 계산하기 위해 알람은 매개변수 배열의 모든 연속 부분 배열을 생성하고, 모든 연속 부분 배열의 i번째 지수 거듭제곱의 합을 계산한다. 부분 배열 Aj, Aj+1, ..., Ak의 i번째 지수 거듭제곱은 Aj × 1i + Aj+1 × 2i + Aj+2 × 3i + ... + Ak × (k-j+1)i로 정의된다. 따라서 POWERi는 매개변수 배열의 모든 연속 부분 배열의 i번째 지수 거듭제곱의 합이다.

예를 들어 i = 2이고 A = [1, 4, 2]라면, A의 i번째 지수 거듭제곱은 다음과 같이 계산된다.

• [1]의 2번째 지수 거듭제곱 = 1 × 12 = 1
• [4]의 2번째 지수 거듭제곱 = 4 × 12 = 4
• [2]의 2번째 지수 거듭제곱 = 2 × 12 = 2
• [1, 4]의 2번째 지수 거듭제곱 = 1 × 12 + 4 × 22 = 17
• [4, 2]의 2번째 지수 거듭제곱 = 4 × 12 + 2 × 22 = 12
• [1, 4, 2]의 2번째 지수 거듭제곱 = 1 × 12 + 4 × 22 + 2 × 32 = 35

따라서 합계는 71이다.

오늘 밤 Shil은 자신의 Kickstart Alarm을 처음 사용한다. 그래서 아침에 알람이 낼 소리가 걱정된다. 이웃을 깨울 수도 있고, 더 나아가 지구 전체를 깨울 수도 있다. 하지만 각 기상 호출의 세기를 계산하는 일은 그에게 매우 어렵다. K와 매개변수 배열 A1, A2, ..., AN이 주어졌을 때, 각 기상 호출의 세기 합, 즉 POWER1 + POWER2 + ... + POWERK를 계산하도록 도와줄 수 있는가?

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 N, K, x1, y1, C, D, E1, E2와 F가 한 줄에 주어진다. N은 배열 A의 길이이고, K는 기상 호출의 수이다. 나머지 값은 다음과 같이 배열 A의 원소를 생성하는 데 사용하는 매개변수이다.

다음 점화식을 사용해 i = 2부터 N까지 xi와 yi를 생성한다.

• xi = ( C × xi-1 + D × yi-1 + E1 ) modulo F.
• yi = ( D × xi-1 + C × yi-1 + E2 ) modulo F.

모든 i = 1부터 N에 대해 Ai = ( xi + yi ) modulo F로 정의한다.

각 테스트 케이스마다 Case #x: POWER 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, POWER는 i = 1부터 K까지의 POWERi 합이다. POWER가 매우 클 수 있으므로 1000000007 (109 + 7)로 나눈 나머지를 출력한다.

• 1 ≤ T ≤ 100.
• 1 ≤ x1 ≤ 105.
• 1 ≤ y1 ≤ 105
• 1 ≤ C ≤ 105.
• 1 ≤ D ≤ 105.
• 1 ≤ E1 ≤ 105.
• 1 ≤ E2 ≤ 105.
• 1 ≤ F ≤ 105.

샘플 케이스 #1에서 매개변수 배열은 [3, 2]이다. 모든 연속 부분 배열은 [3], [2], [3, 2]이다.

i = 1일 때:

• [3]의 1번째 지수 거듭제곱 = 3 × 11 = 3
• [2]의 1번째 지수 거듭제곱 = 2 × 11 = 2
• [3, 2]의 1번째 지수 거듭제곱 = 3 + 2 × 21 = 7

따라서 POWER1은 12이다.

i = 2일 때:

• [3]의 2번째 지수 거듭제곱 = 3 × 12 = 3
• [2]의 2번째 지수 거듭제곱 = 2 × 12 = 2
• [3, 2]의 2번째 지수 거듭제곱 = 3 + 2 × 22 = 11

따라서 POWER2는 16이다.

i = 3일 때:

• [3]의 3번째 지수 거듭제곱 = 3 × 13 = 3
• [2]의 3번째 지수 거듭제곱 = 2 × 13 = 2
• [3, 2]의 3번째 지수 거듭제곱 = 3 + 2 × 23 = 19

따라서 POWER3은 24이다.