问题描述

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

输入数据

从problem4.in中读入一个数N。1<=N<=1000。

输出数据

将答案输出到problem4.out中。由于结果可能很大，你只需要输出这个答案mod 12345的值

样例输入

4

样例输出

9