奶牛散步

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

时间限制：10000

内存限制：131072

输入

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

输出

输出有多少方案数模12345

样例输入

2

样例输出

7