Problem 1208. -- 奶牛散步

1208: 奶牛散步

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 190  Solved: 90
[Submit][Status][Web Board]

Description

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

Input

一个数字,代表N,1<=N<=1000

Output

输出有多少方案,结果巨大,将输出mod 12345的结果. 

Sample Input

2

Sample Output

7

HINT

Source

[Submit][Status]