Factorial Root
Турнир за Купата на Декана, 2011
Time Limit: 0.1s, Memory Limit: 64MiB
Дигитален корен (Digital Root, DR) на едно число се нарича итеративното събиране на цифрите му, докато сборът не стане едноцифрен. Например ако входното число е 1337, то неговият дигитален корен би бил 1337 => 1 + 3 + 3 + 7 = 14 => 1 + 4 = 5, тоест DR(1337) = 5. Дигиталният корен на 42 пък се намира след само една итерация: 4 + 2 = 6. Като трети пример 666 => 6 + 6 + 6 = 18 => 1 + 8 = 9, тоест DR(666) = 9.

Факториел на естествено число N се бележи N! и се дефинира като:
  • F(N) = 1, за N = 0
  • F(N) = N * F(N – 1), за N > 0

Ели комбинира двете функции за да получи Factorial Root. Функцията на момичето представлява дигиталният корен на N факториел, тоест DR(N!). Помогнете на Ели като напишете програма, която го намира дори за сравнително големи стойности.
Вход
На единствен ред на стандартния вход ще бъде зададено цялото число N.
Изход
На стандартния изход изведете една единствена десетична цифра – резултата от DR(N!).
Ограничения
  • 1 ≤ N ≤ 1,000,000
Примерен Вход Примерен Изход
46
53
179
DR(4!) = DR(24) = 2 + 4 = 6.
DR(5!) = DR(120) = 1 + 2 + 0 = 3.
DR(17!) = DR(355687428096000) = DR(63) = 9.
Мрън!