题⽬描述(Description)

众所周知，⻩⻩同学早晨起来是要刷⽛的。 ⻩⻩同学有N⽀⽛刷，⼜有N个⽛刷套,开始的时候，⼀⽀⽛刷对应放在⼀个⽛刷套中。可是有⼀天， ⻩⻩同学把所有⽛刷套⾥的⽛刷都拿出来，玩了⼀会⼉，他⼜要把所有的⽛刷都放回去。可是，他忽然 ⼀想，我可不可以使得没有任何⼀⽀⽛刷放回它原来的⽛刷套⾥⾯呢? ⻩⻩同学努⼒试了很久，却⼀直没有成功过⼀次。于是他断定这个要求是⽆法达成的，你怎么认为的 呢?

输⼊格式(Format Input)

输⼊⽂件put.in只包括⼀个整数N，表示⽛刷和⽛刷套的总数。

输出格式(Format Output)

输出⽂件put.out，如果存在满⾜要求的⽅法，输出放法⽅案总数L。因为⽅案总数可能⽐较⼤，所以你可 以将答案Mod 1206后再输出。如果不存在满⾜要求的⽅法，则输出"No Solution!”

输⼊样例 1(Sample Input 1)

3

输出样例 1(Sample Output 1)

2

限制(Restrictions)

时间限制(Time Limit): 1000 ms

内存限制(Memory Limit): 65536 KB

说明/提示

对于40％的数据，保证N≤9

对于100％的数据，保证N≤100000