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