There are p points on the circle numbered from 0 to (p - 1) in a way that from the point 0 you can move to the point 1, from the point 1 — to the point 2, and so on, and from the point (p - 1) you can move to the point 0.
A chip is initially placed at the point 0. It starts to jump around the circle, first moving 1 point forward, then 2 points forward, then 3 points forward and so on.
How many unique points (including the start one) will be visited by a chip after n moves?
The input has two integers p and n (1 ≤ p ≤ 107, 0 ≤ n ≤ 1018) — the number of points on a circle and the number of moves.
Output a single integer — the number of unique points visited by a chip.
3 10
2
5 3
3
8 1000000000000000000
8
Name |
---|