问题描述

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

输入数据

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

输出数据

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

样例输入

2

样例输出

7