7.2.5 Description has only two Sentences

Problem Description

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.

 

Input

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

 

Output

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

 

Sample Input

2 0 9

 

Sample Output

1

 

Author

WhereIsHeroFrom

思路：不会。。贴题解吧

http://followmyheart1991.blog.163.com/blog/static/178648807201161812739106/