lakhanamdhari / chef-and-cake

Another tricky problem

Problem : chef and cake

The Chef once decided to prepare some nice dishes on his birthday. There are N items kept on his shelf linearly from position 1 to N. Taste of the i-th item is denoted by a integer A_i.

He wants to make Q dishes. A dish will be made using some ingredients in the continuous range A_L., A_{L + 1}., , , A_R. (1-base indexing). Quality of the dish will be determined by the ingredient with minimum taste. Chef wants help of his assistant Rupsa to find out sum and product of qualities of the dishes. As product of the qualities of the dishes could be very large, print it modulo 10⁹ + 7. Also, you are given an integer K and you are assured that for each dish, the size of continuous range of the ingredients (i.e. R - L + 1) will always lie between K and 2 * K, both inclusive.

Method of generation of Array A

You are given non-negative integer parameters a, b, c, d, e, f, r, s, t, m, A[1]

for x = 2 to N:
	if(t^x mod s  <= r)        // Here t^x signifies "t to the power of x"
		A[x] = (a*A[x-1]^2 + b*A[x-1] + c) mod m
	else
		A[x] = (d*A[x-1]^2 + e*A[x-1] + f) mod m

Method of generation of range of ingredients for Q dishes You are given non-negative integer parameters L1, La, Lc, Lm, D1, Da, Dc, Dm

for i = 1 to Q:
	L1 = (La * L1 + Lc) mod Lm;
	D1 = (Da * D1 + Dc) mod Dm; 
	L = L1 + 1;
	R = min(L + K - 1 + D1, N);

Input

The first line contains three integers N, K and Q. The second line contains the integers a, b, c, d, e, f, r, s, t, m, and A[1]. Then third line contains the integers L1, La, Lc, Lm, D1, Da, Dc, and Dm

Output

Output two space separated integers: The sum of qualities of the dishes. The product of qualities of the dishes modulo 10⁹.+7.

Constraints

1 ≤ N, Q ≤ 10⁷

1 ≤ K ≤ N

0 ≤ a, b, c, d, e, f, r, s, t, m, A[1] ≤ 10⁹+7

1 ≤ Lm ≤ N - K + 1

1 ≤ Dm ≤ K + 1

1 ≤ La, Lc ≤ Lm

1 ≤ Da, Dc ≤ Dm

1 ≤ L1 ≤ N

1 ≤ D1 ≤ K

Sub tasks

Subtask #1: 1 ≤ N, Q ≤ 1000 (10 points)

Subtask #2: 1 ≤ Q ≤ 10⁴ (20 points)

Subtask #3: original constraints (70 points)

Example

Input:

4 2 1

1 1 1 1 1 1 1 1 1 100 1

1 1 1 3 1 1 1 2

Output:

13 13

Explanation

The array A comes out to be {1, 3, 13, 83} and the first dish has L = 3 and R = 4. The minimum in this range is 13, thus the sum and product both are 13 and hence the answer.