吉林省信息学奥赛2017冬令营 Day1.T2

净月潭航线

总时间限制:1000ms 内存限制:256 MB

问题描述

净月潭国家森林公园是吉林省著名的 5A 级景区，因为公园中有一深潭而命名，这个深潭是圆形的，
吉林省的 OIER 们要在圆潭的边上建 N 个码头，用以建立航线（可能为 0 条航线）
航线只能是一个码头到另一个码头，并且多条航线之间不能相交，共用码头也算相交。
请 OIER 们算一下，共有多少建立航线的方案？

输入格式

从文件 route.in 中输入数据。
一行一个数 N

输出格式

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

样例输入

4

样例输出

9

提示

数据规模与约定
对于 30%数据：N ≤ 10
对于 50%数据：N ≤ 100
对于 100%数据：N ≤ 1000

实现代码

···

题解