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 (10^{9}+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[0] = 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