Problem Brief

Paint the Ceiling

INTERNOA

You want to build yourself a house. The building company you hired can only build houses with sides from their specific set s. That means they can build you a square house or a rectangular one but if and only if its length and width belong to the sets.

This month, they have a special promotion: they will paint the ceiling of a new house for free... but only if its area is not more than a. You want them to do it for free but you also want to be sure that the house will be comfortable and not too small. How many possible house configurations can you create to have the ceiling painted for free given the side lengths offered?

There is a method to how the company decides what lengths of sides to produce. To determine n lengths of wall segments to offer, they start with a seed value s0, some variables k, b and m, and use the following equation to determine all other side lengths s_i:

s_i = (( k * s_{i-1} + b)mod m+1+s_{i-1}) for 1 <= i < n

Function Description

Complete the function paintTheCeiling in the editor.

paintTheCeiling has the following parameters:

s0: an integer, the seed value for side lengths
n: an integer, the number of side lengths to produce
k: an integer
b: an integer
m: an integer
a: a long integer, the maximum area for a free paint job

Returns

long integer: the number of possible house configurations

1Example 1

Input

s0 = 2, n = 3, k = 3, b = 3, m = 2, a = 15

Output

Explanation

Now that we have our set of lengths, we can brute force the solution using the following tests assuming a=15:

s=[2,4,6]

s1 s2 s1xs2 s1xs2≤a

2 2 4 True

2 4 8 True

2 6 12 True

4 2 8 True

4 4 16 False

4 6 24 False

6 2 12 True

6 4 24 False

6 6 36 False

There are 5 combinations that will result in a free paint job. Brute force will not meet the time constraints on large sets.

Constraints

Limits and guarantees your solution can rely on.

1 ≤ n ≤ 6 x 10^6
1 ≤ s_i ≤ 10^9
1 ≤ k, b, m ≤ 10^9
1 ≤ a ≤ 10^18