Description has only two Sentences

a_n = X*a_n-1 + Y and Y mod (X-1) = 0.
Your task is to calculate the smallest positive integer k that a_k mod a₀ = 0.

Each line will contain only three integers X, Y, a₀ ( 1 < X < 2³¹, 0 <= Y < 2⁶³, 0 < a₀ < 2³¹).

For each case, output the answer in one line, if there is no such k, output "Impossible!".

2 0 9

1

WhereIsHeroFrom

HDOJ Monthly Contest – 2010.02.06