Вам дано натуральное число m. Требуется найти произведение всех натуральных чисел не превосходящих m и взаимно простых с m, и выдать его остаток при делении на m.
В единственной строке входного файла задано натуральное число m ≤ 10^18.
В единственную строку выходного файла выведите ответ на задачу.