Description

“心无界则天地宽,当狂风在你耳边呼啸时,你只当它微风拂面;当暴雨在你眼前倾泻时,你只当它细雨绵绵;当闪电在你头顶肆虐时,你只当它萤火流逝。人,绝不能在逆境面前屈服·....·哎,不说了,又到做操时间了,再晚典狱长要骂人了。” 每天早晨，监狱里的囚犯都必须排成一行,随着“左三圈,右三圈,脖子扭扭,屁股扭扭早睡早起,咱们来做运动!”的歌声做操。试计算 n个囚犯排成一排,共有多少种排列方法并将排列方法打印出来.

Format

Input

一个整数即n。

Output

输出每种方案,每种方案各占一行。最后一行为方案数

Samples

2

12
21
2

Limitation

1s, 1024KiB for each test case.