计算出n个整数的全排列种数，并按升序输出这所有的排列。假设这n个整数是 1 ~ n。
一个整数 n ( 1 ≤ n ≤ 9 )
每行一个排列，每个数字之间以空格隔开，最后一行输出总行数。
样例输入
3
样例输出
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 6