2995. 全排列

【题目描述】

编程求$1\sim n$所有自然数的全排列方案及其总方案数。

【输入格式】

一个正整数$n(n\leq 8)$。

【输出格式】

按字典序从小到大输出所有全排列方案，数字用空格隔开；

最后一行输出总方案数。

【样例输入】

3

【样例输出】

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
6