题目描述

给定 $n$，求 $n$ 个元素的错排方案数。

错排是指一个排列中所有元素都不在自己原来位置上的排列。例如对于 $n=3$，排列 $(2,3,1)$ 和 $(3,1,2)$ 都是错排，因此 $n=3$ 时错排方案数为 $2$。

错排公式的递推关系为：

$$f[1]=0,\quad f[2]=1,\quad f[n]=(f[n-1]+f[n-2])\times(n-1)\ (n\ge 3)$$

请分别用数组递推和滚动变量优化两种方式实现，并输出答案进行对比。

输入格式

一行一个整数 $n$。

输出格式

输出两行，每行一个整数，分别为数组递推方式得到的错排方案数与滚动变量优化方式得到的错排方案数（两者应相同）。

10

1334961
1334961

提示

$1\le n\le 20$（本题 $n$ 需要较小，因为错排方案数增长很快，$n$ 过大时 long long 会溢出）。

注意边界情况：当 $n=1$ 时，滚动变量方式中 $c$ 的初始值并不等于 $f[1]$，需要特判输出 $0$。