题目描述

在一个坐标系中，某人从原点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？

输入格式

读入一个数N。1<=N<=1000。

输出格式

一个整数，表示答案。

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

样例

input

2

output

7

限制与提示

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$