503007 - 圆的分割

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

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

Input

输入一个整数N。

Output

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

Examples

Input

4

Output

9

Hint

方案数如图3.9所示。

图3.9

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题