Добуток взаємно простих

Вам задано натуральне число m. Потрібно знайти добуток всіх натуральних чисел, що не перевищують m і взаємно прості з m, і вивести його остачу при діленні на m.

Вхідні дані

У єдиному рядку вхідного файлу задано натуральне число m ≤ 10^18.

Вихідні дані

У єдиний рядок вихідного файлу виведіть відповідь до задачі.

Приклади