# SRM 7861500ModCounters

## Problem Statement

You are given N "512-Modulo counters". Each 512-Modulo counter contains a value that is between 0 and 511, inclusive. Each counter allows an incrementation operation. Let's say the value of counter is x, then after the incrementation the value of counter will be (x + 1) % 512.

You are given an array S of length N with the initial value of each counter. Now, you are planning to perform K steps. In each step, you select a counter uniformly at random from the given N counters and increment it. You need to find the expected sum of the array after K steps. (Note that the sum is computed exactly, not modulo 512.)

Let your answer be R/Q, then you need to return (R*Q-1) modulo (109+7). See Notes for the explanation of Q-1.

You are given integers A0, X, Y, N and an integer array P. Use the pseudocode below to generate the array S.

```A = A0
for i = 1 to N-1:
A[i] = (A[i-1] * X + Y) modulo 1812447359

S = P
for i = size(P) to N-1:
S[i] = A[i] modulo 512
```

## Definition

• Class ModCounters
• Method findExpectedSum
• Parameters vector<int> , int , int , int , int , int
• Returns int
• Method signature int findExpectedSum(vector<int> P, int A0, int X, int Y, int N, int K)
(be sure your method is public)

## Limits

• Time limit (s) 2.000
• Memory limit (MB) 256

## Notes

• It can be shown that the expected value of the sum of all counters is always a rational number R/Q such that Q and 1000000007 are relatively prime.
• Q-1 denotes the inverse element to Q when computing modulo 1000000007. That is, (Q * Q-1) mod 1000000007 = 1.

## Constraints

• The length of P will be between 0 and min(N, 100) (inclusive)
• Integers in P will be between 0 and 511 (inclusive)
• A0 will be between 0 and 1812447358 (inclusive)
• X will be between 0 and 1812447358 (inclusive)
• Y will be between 0 and 1812447358 (inclusive)
• N will be between 1 and 2000000 (inclusive)
• K will be between 1 and 500000000 (inclusive)

## Test cases

1. input
• P { 0, 511 }
• A0 0
• X 0
• Y 0
• N 2
• K 1
output
Returns 256
note
After one step, the array has two equiprobable states : {0, 0} and {1, 511}. Hence, the expected sum = (0 + 512) / 2 = 256.
2. input
• P { 0 }
• A0 1001
• X 1001
• Y 1001
• N 2
• K 2
output
Returns 508
note
Here, the array is {0, 506}. Note that in the final array, the sum will be 508, independent of which counters are chosen in each step. Hence, the expected sum is 508.
3. input
• P { }
• A0 3583
• X 1000
• Y 1812447358
• N 2
• K 2
output
Returns 152
note
The array is {511, 23}. After 2 steps : the possible outcomes are {1, 23}, {0, 24}, {0, 24}, {511, 25}. Hence, the expected sum = 608 / 4 = 152.
4. input
• P { 100, 101 }
• A0 5000
• X 50000
• Y 100000
• N 1000
• K 1000
output
Returns 856925612
5. input
• P { }
• A0 100000000
• X 100000000
• Y 100000000
• N 10
• K 1000
output
Returns 454731206
6. input
• P { }
• A0 501296088
• X 234548363
• Y 703491623
• N 2000000
• K 1894643
output
Returns 804222535

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.