Module: Fast exponentiation


Problem

3 /5


Application of Fermat's Little Theorem

Problem

Given a number a and a prime number p. Find the minimum number x such that \((a * x) \% p = 1\).


Input
The input is two natural numbers ap (\(a,\ p <= 10^ {18} \)).

Imprint
Print the answer to the problem.
 

 

Examples
# Input Output
1 2 5 3