Description

【问题描述】

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

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

Input Format

文件只有一行为一个正整数n

Output Format

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

4​

9​

Hint

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