问题描述

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

输入格式

输入一个数N。

输出格式

输出一个数。由于结果可能很大，你只需要输出这个答案mod 12345的值。

样例

4

9

数据范围

$0<N<1000$

来源

• 信息学奥赛之数学一本通
• stong9070整理