圆弦

Grade 0 Open Time Wednesday, 16 January 2013, 3:05 pm
Discount 0.8 Time Discount Wednesday, 16 January 2013, 3:05 pm
Allow late Yes Close Time Wednesday, 16 January 2013, 3:05 pm
Input file circlex.in Output file circlex.out

【问题描述】

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

     例如:n =4时,f(n)=9。方案如图

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

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

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

输出:
circlex.out
9

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