题目描述

$n$ 的阶乘 $n! = 1 \times 2 \times 3 \times \dots \times n$ 增长得非常快：$10! = 3628800$，$20!$ 已经接近 long long 的上限，而 $100!$ 足足有 $158$ 位。

小华对大数的「长相」很好奇。给定正整数 $n$，请你求出 $n!$ 的：

1. 十进制位数；
2. 各位数字之和；
3. 末尾连续 $0$ 的个数。

输入格式

一行一个正整数 $n$。

输出格式

输出三行，每行一个整数，依次表示 $n!$ 的位数、各位数字之和、末尾连续 $0$ 的个数。

样例 #1

样例输入 #1

10

样例输出 #1

7
27
2

样例解释

$10! = 3628800$，共 $7$ 位；各位数字之和为 $3+6+2+8+8+0+0 = 27$；末尾有 $2$ 个 $0$。

提示

数据范围

• 对于 $20\%$ 的数据：$n \le 20$；
• 对于 $50\%$ 的数据：$n \le 100$；
• 对于 $100\%$ 的数据：$1 \le n \le 3000$。

提示

• $3000!$ 有 $9131$ 位，必须用高精度：用数组倒序存储每一位（d[0] 存个位），从 $2$ 乘到 $n$，每次做一遍「高精度 × 低精度」。
• 乘法时，每一位乘以 $i$ 再加上进位，本位留下 % 10，进位为 / 10；最后的进位可能有好几位，要不断往高位写。
• 中间结果最大约为 $9 \times 3000 +$ 进位，用 int 就够了。