时间限制：1秒　　内存限制：256M

---

【题目描述】

　　所谓的凹形队列，就是一个 \(1 \sim N\) 的全排列 \(P_1,P_2,…,P_N\) ，当且仅当存在某个 \(k\) 使得：

　　　　　　　\(P_1 > P_2 > ... > P_k < P_{k+1} < ... < P_N\)

　　比如 \(N=7\) 时，那么全排列，7631245 是凹形队列，7654321 也是凹形队列，当然，1234567也是凹形队列，但 3562147 就不是。

　　请编程，输入 \(N\) ，输出凹形队列的个数和所有可能的方案。

【输入格式】

　　一个正数 \(N\)。

【输出格式】

　　第一行输出 \(1 \sim N\) 的全排列中凹形队列的个数。
　　接下来若干行按字典序输出所有可能的凹形队列。

【输入输出样例】

　Input

4

　Output

8
1 2 3 4
2 1 3 4
3 1 2 4
3 2 1 4
4 1 2 3
4 2 1 3
4 3 1 2
4 3 2 1

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤20\)。

【来源】

　　Mr.he