Задача Дигитация

Описание

В некоторых задачах встречается такая функция от целого числа, как сумма цифр. Например, установить, делится ли число на 9, достаточно просто: нужно лишь определить, делится ли сумма цифр числа на 9.

Рассмотрим обобщение суммы цифр числа - дигитацию . А именно, если сумма цифр числа s(x) состоит из одной цифры, то дигитация d(x) равна s(x). Иначе, применяем s(x) к сумме цифр, пока результат не будет состоять из одной цифры. Это можно выразить короче: d(x) = d(s(x)).

Задано число n. Необходимо вычислить дигитацию факториала этого числа: d(n!) = d(1 * 2 * ... * n).

Формат входных данных

В первой строке входного файла содержится единственное число n (1 <= n <= 10 ⁹ ).

Формат выходных данных

В выходной файл выведите дигитацию n!.