【问题描述】

众所周知，黄黄同学早晨起来是要刷牙的。

黄黄同学有N支牙刷，又有N个牙刷套，开始的时候，一支牙刷对应放在一个牙刷套中。可是有一天，黄黄同学把所有牙刷套里的牙刷都拿出来，玩了一会儿，他又要把所有的牙刷都放回去。可是，他忽然一想，我可不可以使得没有任何一支牙刷放回它原来的牙刷套里面呢?

黄黄同学努力试了很久，却一直没有成功过一次。于是他断定这个要求是无法达成的，你怎么认为的呢?

【输入文件】

输入文件put.in只包括一个整数N，表示牙刷和牙刷套的总数。

【输出文件】

输出文件put.out，如果存在满足要求的方法，输出放法方案总数L。因为方案总数可能比较大，所以你可以将答案模 1206后再输出。如果不存在满足要求的方法，则输出"No Solution!”

【样例输入】

3

【样例输出】

2

【数据范围】

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

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