### Problem :

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 _{1}**,

**A**, …,

_{2}**A**. In the morning, the clock will ring

_{N}**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**is defined as

_{k}**A**× 1

_{j}^{i}+

**A**× 2

_{j+1}^{i}+

**A**× 3

_{j+2}^{i}+ … +

**A**× (k-j+1)

_{k}^{i}. 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`

^{2}= 1 - 2-nd exponential-power of
`[4] = 4 × 1`

^{2}= 4 - 2-nd exponential-power of
`[2] = 2 × 1`

^{2}= 2 - 2-nd exponential-power of
`[1, 4] = 1 × 1`

^{2}+ 4 × 2^{2}= 17 - 2-nd exponential-power of
`[4, 2] = 4 × 1`

^{2}+ 2 × 2^{2}= 12 - 2-nd exponential-power of
`[1, 4, 2] = 1 × 1`

^{2}+ 4 × 2^{2}+ 2 × 3^{2}= 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 _{1}**,

**A**, …,

_{2}**A**, can you help him by calculating the summation of power of each wakeup call: POWER

_{N}_{1}+ POWER

_{2}+ … + POWER

_{K}?

**Input :**

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 _{1}, y_{1}, C, D, E_{1}, E_{2}** 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_{1}**F**. - y
_{i}= (**D**× x_{i-1}+**C**× y_{i-1}+**E**) modulo_{2}**F**.

We define **A _{i}** = ( x

_{i}+ y

_{i}) modulo

**F**, for all i = 1 to

**N**.

**Output :**

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^{9} + 7).

**Limits :**

1 ≤ **T** ≤ 100.

Time limit: 90 seconds per test set.

Memory limit: 1 GB.`1 ≤ `

**x _{1}** ≤ 10

^{5}.

1 ≤

**y**≤ 10

_{1}^{5}

1 ≤

**C**≤ 10

^{5}.

1 ≤

**D**≤ 10

^{5}.

1 ≤

**E**≤ 10

_{1}^{5}.

1 ≤

**E**≤ 10

_{2}^{5}.

1 ≤

**F**≤ 10

^{5}.

**Small dataset (Test set 1 – Visible) :**

`1 ≤ `

.**N** ≤ 100.

1 ≤ **K** ≤ 20

**Large dataset (Test set 2 – Hidden) :**

`1 ≤ `

.**N** ≤ 10^{6}.

1 ≤ **K** ≤ 10^{4}

**Sample :**

Input |

2 2 3 1 2 1 2 1 1 9 10 10 10001 10002 10003 10004 10005 10006 89273 |

Output |

Case #1: 52 Case #2: 739786670 |

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
^{1}= 3 - 1-st Exponential-power of [2] = 2 × 1
^{1}= 2 - 1-st Exponential-power of [3, 2] = 3 + 2 × 2
^{1}= 7

So POWER_{1} is 12.

For i = 2:

- 2-nd Exponential-power of [3] = 3 × 1
^{2}= 3 - 2-nd Exponential-power of [2] = 2 × 1
^{2}= 2 - 2-nd Exponential-power of [3, 2] = 3 + 2 × 2
^{2}= 11

So POWER_{2} is 16.

For i = 3:

- 3-rd Exponential-power of [3] = 3 × 1
^{3}= 3 - 3-rd Exponential-power of [2] = 2 × 1
^{3}= 2 - 3-rd Exponential-power of [3, 2] = 3 + 2 × 2
^{3}= 19

So POWER_{3} is 24.

### Solution :

```
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = pow(10,9)+7;
ll getPow(ll a,ll p){
ll ret = 1,cp = a;
while(p){
if(p&1) ret = (ret*cp)%MOD;
p >>= 1;
cp = (cp*cp)%MOD;
}
return ret;
}
ll getK(ll i,ll k){
if(i == 1) return k%MOD;
ll ret = ((i*(getPow(i,k)-1)%MOD)*getPow(i-1,MOD-2))%MOD;
return ret;
}
int main(){
int T;
cin >> T;
for(int k = 1; k <= T; ++k){
ll N,K,x1,y1,C,D,E1,E2,F;
cin >> N >> K >> x1 >> y1 >> C >> D >> E1 >> E2 >> F;
vector<ll> A(N);
A[0] = (x1+y1)%F;
ll CD = C+D,E = E1+E2;
for(ll i = 1; i < N; ++i) A[i] = (CD*A[i-1]+E)%F;
ll psum = 0,nb = 1,kval = N,ret = 0;
for(ll i = N-1; i >= 0; --i){
psum = (psum+nb*A[i])%MOD;
++nb;
ret = (ret+psum*getK(kval,K))%MOD;
--kval;
}
cout << "Case #" << k << ": " << ret << "\n";
}
return 0;
}
```

148 total views, 3 views today

#### Post Disclaimer

*The hole problem statement are given by codingcompetitions.withgoogle.com but the solution are generated by the sltechnicalacademy authority if any of the query regarding this post or website fill the following contact form thank you. *