时间限制：1秒　　内存限制：256M

---

【题目描述】

　　从一个无限大的矩阵的中心点出发，一步只能向右走、向上走或向左走。恰好走 \(N\) 步且不经过已走的点共有多少种走法？

【输入格式】

　　一个数字，代表 \(N\)。

【输出格式】

　　输出有多少方案。这个数可能很大，你需要 \(mod\ 12345\) 后输出。

【输入输出样例】

　Input

2

　Output

7

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤1000\)

【来源】

　　Mr.he