Description has only two Sentences

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 3307
64-bit integer IO format: %I64d      Java class name: Main

Description

an = X*an-1 + Y and Y mod (X-1) = 0.
Your task is to calculate the smallest positive integer k that ak mod a0 = 0.

Input

Each line will contain only three integers X, Y, a0 ( 1 < X < 231, 0 <= Y < 263, 0 < a0 < 231).

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

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .