题目背景

“ 如 果 有 来 世 ， 我 们 必 将 再 次 相 遇”

题目描述

你现在需要求一个长度为 $n$ 的序列的末项，其中，第 $i$ 项记为 $a_{i}$。$a_{i} = f_{i} \times i!$。对于 $i \geq 3$，$f_{i}=f_{i-1}+f_{i-2}$，$f_1=1,f_2=2$。$i!=i \times (i-1) \times (i-1) \times \cdots \times 1 = \prod_{i=1}^{n} i$。注意 $n$ 可能很大。

输入格式

一行一个数 $n$，表示求长度为 $n$ 的序列 $a$ 的末项。

输出格式

一行 $1$ 个整数表示 $a_{n}$。特别的，位数多余 $100$ 位只输出末 $100$ 位。

5

960

说明/提示

为防止你骗分，如果这 $100$ 位全部都是 $0$，则在第二行输出两个整数，第一个整数表示答案的第一位，第二个整数表示答案的位数，用空格隔开。

样例解释：

对于 $10 \%$ 的数据，保证 $1 \le n \le 10$，

对于另外 $20 \%$ 的数据，保证 $11 \le n \le 100$，

对于另外 $20 \%$ 的数据，保证 $101 \le n \le 1000$，

对于 $100 \%$ 的数据，保证 $1 \le n \le 10100$。