eolymp
Problems

The largest increasing subsequence

The largest increasing subsequence

Considerthe sequence ofxi,givenby the followingrelations:

x0 = a + b, x1 = a – b,

xi = (a·xi -2 + b·xi - 1) mod m, i > 1

For agivenpositive integer n,find thelength of the longestincreasingsubsequencex0, x1, x2, …, xn.

Input

Eachtestconsists of onelinecontaining thefour naturalnumbersa, b, m, n (ab, 1a, b, m, n106). Number oftestcasesin a singletestdoes not exceed20.

Output

For eachteston a separate lineto derivemaximumlengthof increasingsubsequences.

Time limit 2 seconds
Memory limit 64 MiB
Input example #1
3 1 20 10
5 2 1000 2000
Output example #1
5
70