U294944 错排问题

在书架上放有编号为1，2，…，n的n本书。现将n本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。求满足以上条件的方案共有多少种？由于结果较大，只需输出方案数模12345即可。

输入一个正整数n（1

输出一行，表示错排方案数模12345的值。

4本书有9种放法：{2,1,4,3}{2,3,4,1}{2,4,1,3}{3,1,4,2}{3,4,1,2}{3,4,2,1}{4,1,2,3}{4,3,1,2}{4,3,2,1}