题目描述

一个圆的圆周上有$\red{N}$个点$\red{(0<N<1 000)}$。 连接任意多条（可能是$\red{0}$条）不相交的 弦（共用端点也算相交）共有多少种方案?

输入格式

输人一个数$\red{N}$。

输出格式

输出一个数。由于结果可能很大.你只需要输出这个答案$\red{mod ~12 345}$的值。

样例

输入样例

4

输出样例

9