圆弦

成绩 0 开启时间 2013年01月16日 星期三 15:05
折扣 0.8 折扣时间 2013年01月16日 星期三 15:05
允许迟交 是 关闭时间 2013年01月16日 星期三 15:05
输入文件 circlex.in 输出文件 circlex.out

【问题描述】

     圆周上有N个点。连接任意多条（可能是0条）不相交的弦（共用端点也算相交）共有多少种方案？

     例如：n ＝4时，f(n)=9。方案如图

 
【输入格式】
    文件只有一行为一个正整数n

【输出格式】
   输出文件只有一个整数，方案数(由于结果可能很大，你只需要输出这个答案mod 12345的值。)。

【输入输出样例】
 
输入：
circlex.in
4

输出：
circlex.out
9

数据规模:1<=N<=1000