|
You are given an infinite sequence of integers:
A0 = 0
Ai = ( Ai-1 + q ) mod p, for i > 0
Where p is a prime number, a mod p is reminder of division a by p.
Your task is to count how many integers in the range [0..p-1] are not
included in this sequence. Notice that p can be very large.
Input
The first line contains one prime integer p.
The second line contains one integer q.
(0 ≤ q ≤ p ≤ 10100).
Output
Output a single number – the answer for the problem.
|