时间限制：1秒　　内存限制：256M

---

【题目描述】

　　有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：

　　　a. 每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；
　　　b. 走过的格子立即塌陷无法再走第二次；
　　　c. 只能向北、东、西三个方向走；

　　请问：如果允许在方格矩阵上走 \(n\) 步，共有多少种不同的方案。
　　注意：2 种走法只要有一步不一样，即被认为是不同的方案。
　

【输入格式】

　　允许在方格上行走的步数 \(n\)。

【输出格式】

　　计算出的方案数 \(mod\ 1234567\) 的结果。

【输入输出样例】

　Input

2

　Output

7

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n≤1000\)。

【来源】

　　Mr.he