Wilsons Theorem

medium

Question Solve Solutions

you have been given number n and p, you need to find n! % p (n factorial mod p). p is a prime no.

Input Format

The first line contains the integer n and p.

Output Format

Output an integer in a line containing n! modulo P.

Constraints

1&lt;= n &lt;= 10^9
1&lt;= p &lt;= 10^9
1&lt;= abs(n - p) &lt;= 1000

Example

Input

5 11

Output

Eulers Totient Function

Modular Fast Exponentiation

Related Questions

medium Extended Euclidean Algorithm medium Linear Diophantine Equation hard Eulers Totient Function medium Modular Fast Exponentiation medium Modular C(n,r) hard No Max No Min medium Prime Factors Using Sieve medium All Factors Using Sieve easy Count Of Common Divisors medium Gcd Length medium I Hate 1111 medium Relatively Prime Pairs medium Sum Of Factors easy Chinese Remainder Theorem easy Monkey Tradition