Вам задано натуральне число \textbf{m}. Потрібно знайти добуток всіх натуральних чисел, що не перевищують \textbf{m} і взаємно прості з \textbf{m}, і вивести його остачу при діленні на \textbf{m}. \InputFile У єдиному рядку вхідного файлу задано натуральне число \textbf{m} ≤ \textbf{10^18}. \OutputFile У єдиний рядок вихідного файлу виведіть відповідь до задачі.