23961번 - Kickstart Alarm 서브태스크다국어

문제

Shil has a very hard time waking up in the morning each day, so he decides to buy a powerful alarm clock to Kickstart his day. This Alarm is called a Kickstart Alarm. It comes pre-configured with K powerful wakeup calls. Before going to bed, the user programs the clock with a Parameter Array consisting of the values A₁, A₂, ..., A_N. In the morning, the clock will ring K times, with the i-th wakeup call having power POWER_i.

To calculate POWER_i, the alarm generates all the contiguous subarrays of the Parameter Array and calculates the summation of the i-th exponential-power of all contiguous subarrays. The i-th exponential-power of subarray A_j, A_j+1, ..., A_k is defined as A_j × 1ⁱ + A_j+1 × 2ⁱ + A_j+2 × 3ⁱ + ... + A_k × (k-j+1)ⁱ. So POWER_i is just the summation of the i-th exponential-power of all the contiguous subarrays of the Parameter Array.

For example, if i = 2, and A = [1, 4, 2], then the i-th exponential-power of A would be calculated as follows:

• 2-nd exponential-power of [1] = 1 × 1² = 1
• 2-nd exponential-power of [4] = 4 × 1² = 4
• 2-nd exponential-power of [2] = 2 × 1² = 2
• 2-nd exponential-power of [1, 4] = 1 × 1² + 4 × 2² = 17
• 2-nd exponential-power of [4, 2] = 4 × 1² + 2 × 2² = 12
• 2-nd exponential-power of [1, 4, 2] = 1 × 1² + 4 × 2² + 2 × 3² = 35

so the total is 71.

Tonight, Shil is using his Kickstart Alarm for the first time. Therefore, he is quite worried about the sound the alarm might make in the morning. It may wake up the neighbors, or, worse yet, it may wake up the whole planet! However, calculating the power of each wakeup call is quite difficult for him. Given K and the Parameter Array A₁, A₂, ..., A_N, can you help him by calculating the summation of power of each wakeup call: POWER₁ + POWER₂ + ... + POWER_K?

입력

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of one line with nine integers N, K, x₁, y₁, C, D, E₁, E₂ and F. N is the length of array A, K is the number of wakeup calls. Rest of the values are parameters that you should use to generate the elements of the array A, as follows.

Use the recurrences below to generate x_i and y_i for i = 2 to N:

• x_i = ( C × x_i-1 + D × y_i-1 + E₁ ) modulo F.
• y_i = ( D × x_i-1 + C × y_i-1 + E₂ ) modulo F.

We define A_i = ( x_i + y_i ) modulo F, for all i = 1 to N.

출력

For each test case, output one line containing Case #x: POWER, where x is the test case number (starting from 1) and POWER is the summation of POWER_i, for i = 1 to K. Since POWER could be huge, print it modulo 1000000007 (10⁹ + 7).

제한

• 1 ≤ T ≤ 100.
• 1 ≤ x₁ ≤ 10⁵.
• 1 ≤ y₁ ≤ 10⁵
• 1 ≤ C ≤ 10⁵.
• 1 ≤ D ≤ 10⁵.
• 1 ≤ E₁ ≤ 10⁵.
• 1 ≤ E₂ ≤ 10⁵.
• 1 ≤ F ≤ 10⁵.

Test Set 1 (13점)

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

Test Set 2 (26점)

• 1 ≤ N ≤ 10⁶.
• 1 ≤ K ≤ 10⁴.

힌트

In Sample Case #1, the Parameter Array is [3, 2]. All the contiguous subarrays are [3], [2], [3, 2].

For i = 1:

• 1-st Exponential-power of [3] = 3 × 1¹ = 3
• 1-st Exponential-power of [2] = 2 × 1¹ = 2
• 1-st Exponential-power of [3, 2] = 3 + 2 × 2¹ = 7

So POWER₁ is 12.

For i = 2:

• 2-nd Exponential-power of [3] = 3 × 1² = 3
• 2-nd Exponential-power of [2] = 2 × 1² = 2
• 2-nd Exponential-power of [3, 2] = 3 + 2 × 2² = 11

So POWER₂ is 16.

For i = 3:

• 3-rd Exponential-power of [3] = 3 × 1³ = 3
• 3-rd Exponential-power of [2] = 2 × 1³ = 2
• 3-rd Exponential-power of [3, 2] = 3 + 2 × 2³ = 19

So POWER₃ is 24.