503007 - 圆的分割

【题目描述】圆的分割(split)

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

输入

输入一个整数N。

输出

由于结果可能很大,只需输出这个答案 mod 12345的值。

样例

输入

4

输出

9

提示

方案数如图3.9所示。

图3.9

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题