Problem Description

You are given a positive integer m. Calculate the product of all positive integers less then or equal to m and coprime with m, and give the answer modulo m.

Input

There are multiple tests end with EOF, each test contains only a positive integer m ≤ 10^9 in a line. The number of tests is no more than 5000.

Output

In the output file you should write the answer to the task.

1
2
3
4
5
6
7

0
1
2
3
4
5
6