Given an integer ` N`, compute the value of

`.`

**(N-1)! mod N**## Input

` N`, on a single line.

## Output

The value of the expression, on a single line.

## Constraints

**2 ≤ N ≤ 10**^{9}**You will receive full feedback for this problem.**

## Samples

Input | Output | Explanation |
---|---|---|

4 | 2 | N = 4(N-1)! = (4-1)! = 3! = 6 6 mod 4 = 2 |

42 | 0 |

Let us consider two disjoint cases:

is a composite number. In this case, we wish to use the factorization of**N**:**N**- If
can be written as a product of two different integers (**N**), it means that both**N = A × B, 1 < A < B < N**and**A**appear in the product**B**. Therefore,**1 × 2 × … × (N-1)**divides the product.**N** - If
cannot be written as a product of two**N****different**integers, it means thatcan be written as a product of two**N****identical**integers (remember thatis a composite number). Each of the two numbers is equal to**N**.**sqrt(N)**

Becausefor any**1 < sqrt(N) < 2×sqrt(N) < N**greater than**N****4**^{[1]}, both square roots will appear somewhere in the product. Therefore,**1 × 2 × … × (N-1)**divides the product.**sqrt(N) × sqrt(N) = N**

^{[1]}:is a particular case and should be dealt with independently.**N = 4**- If
is a prime number. In this case, we make use of Lagrange's Theorem, which states that the residue classes**N**are a field. This means that every non-zero integer**(mod N)**has a unique multiplicative inverse**a**.**a**^{-1}- For the most part,
. These means that we can match elements in pairs such that each pair has a product congruent to**a ≠ a**^{-1}.**1 (mod N)** - However, there might be some elements
for which**a**. This is equivalent to**a ≡ a**^{-1}(mod N). Because a polynomial of degree**a**^{2}≡ 1 (mod N)has at most**2**roots in any field (again, Lagrange), we can be sure that the only values of**2**for which the previous equation holds are**a**. This means that**±1**(or**±1**and**1**, if you wish) are their own multiplicative inverses. As a consequence, we cannot pair**N-1**with itself, and we cannot pair**1**with itself. However, we can pair**N-1**with**1**, and get a multiplicative residue of**N-1**.**N-1**

pairs with products congruent to**(N-3)/2**, and exacty**1****one**pair with the product congruent to. The following expression will hold:**N-1**. Therefore, the answer in this case is**1 × 2 × … × (N-1) ≡ N-1 (mod N)**.**N-1**- For the most part,

You can find more info on Wikipedia's article on Wilson's theorem.

The problem is reduced to determining whether or not ` N` is a prime number. This can be solved in

`time complexity.`

**O(sqrt(N))**## Python solution (Sergiu Puscas)

1 import math 2 n = input() 3 4 print 2 if n == 4 else (0 if any(n % x == 0 for x in range(2, int(math.sqrt(n))+1)) else n-1)

## Ruby solution (Croitoru Radu Bogdan)

1 require 'prime' 2 3 n = gets.chomp.to_i 4 puts n==4? 2:(Prime.prime?(n)? n-1:0)

## C++ solution (Gabriel Inelus)

1 #include <iostream> 2 int N, p; 3 int main() { 4 std::cin >> N; 5 for(int i = 2; i * i <= N && !p; ++i) 6 p |= (N % i == 0); 7 8 if(N == 4) std::cout << 2; 9 else if(p) std::cout << 0; 10 else std::cout << N - 1; 11 12 return 0; 13 }