Calculating the sum of digits of a factorial of a number

Java Hard math

Task «Calculating the sum of digits of a factorial of a number»

Given a natural number n (1 ≤ n ≤ 1000). It is necessary to calculate the sum of the digits of the number n!. The use of built-in Java types for large numbers (BigInteger) is prohibited. Implement a large number multiplication algorithm manually, using an array of digits. Output a single integer — the sum of the digits of n!.

Input Format

One integer n (1 ≤ n ≤ 1000).

Output Format

One integer — the sum of the digits of n!.

Examples

Example 1

INPUT

5

OUTPUT

3

Example 2

INPUT

10

OUTPUT

27

Example 3

INPUT

1 10

OUTPUT

1

Example 4

INPUT

10 20

OUTPUT

27

main.java