Голова профессора Интегралова
С Монте-Карло Котигорошко и Пан Коцкий полетели самолётом в Лондон, где их уже ждал Вернигора. Вместе с нашими героями летел профессор Интегралов, которого пригласили на международный симпозиум. Профессор решил продемонстрировать свою способность быстро и безошибочно выполнять сложные математические вычисления. "Предположим, – сказал профессор, – что у нас есть N – некоторое натуральных число. Сначала вычислим факториал этого числа, то есть N!, а после этого вычислим сумму всех цифр, составляющих число N!. Если сумма окажется больше 9, нужно опять вычислить сумму уже для полученного числа и эту процедуру повторять до тех пор, пока не получим число в диапазоне от 1 до 9. Понятно?".
"Да" – ответил Котигорошко.
Ну а дальше случилось чудо. Какое б начальное число не называли Котигорошко и Пан Коцкий, профессор не моргнув глазом, тут же называл верный ответ – число от 1 до 9.
Попробуйте написать программу, которая моделировала бы интеллектуальные способности профессора Интегралова.
Входные данные
Первая строка входного файла содержит единственное число N (1 ≤ N ≤ 10^9).
Выходные данные
В выходной файл выведите одно единственное число, которое сообщал профессор Интегралов нашим героям.