曹文信息在线OJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

2398: 奶牛散步

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：46 Solved：28
SubmitSubmit RecordStatisticsWeb BoardShowOff!

Description

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


Input

 一个数字，代表N,N<=1000。

Output

 输出有多少方案,对12345取模。

Sample Input Copy 

2

Sample Output Copy 

7

Source/Category