从一个无限大的矩阵的中心点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点。
共有多少种走法？
一个数字，代表N,N<=1000
输出有多少种方案，答案模 12345
样例输入
2
样例输出
7
样例解释
注：openjudge日常坑人（指题面没说要取模但是因为数据规模太大所以要把结果%12345
最终分组有3组（分别有2，1和3头奶牛在组里）