Description

枫叶晴在 子科技大学 少 可校区养了一棵骆驼刺，它会向地下扎根，每天向下扎一层，$n$ 天后根系形成一个 $n$ 层的等边三角形（具体形态见 Note 部分）。

第 $i$ 天下方会有 $i$ 个位置可以扎根，每个位置的根可以选择下面和它相邻的两个位置（注意：扎根的方向只能向下），向左下角扎根，或者向右下角扎根，也可以同时向左下和右下扎根（分叉），也可以选择不扎根。

由于 少 可校区极度缺水，骆驼刺会保证把根扎到等边三角形的每一个位置。

但是由于尼电生态系统的脆弱性，根系之间不能有交叉，否则骆驼刺会缺水而寄。换句话说，上一层的两个根尖不能向下层的同一个位置扎根（详见图例）。

骆驼刺在尼电的地下快乐地生根了 $n$ 天，根系到达了 $\frac{n(n+1)}{2}$ 个位置，但是枫叶晴看不到它根系的样子，而且他数学很差，他想让你帮他计算，$n$ 层的地下的根系一共有多少种可能的形状？（两个根系存在同一个位置扎根方向不同就是不同形状）

由于答案可能很大超出 int 范围，你只需要告诉枫叶晴答案对 $276276276$ 取余后的结果。

Input

一个整数 $n$（$2\le n\le 10^3$），表示骆驼刺扎根的深度。

Output

一行一个整数，表示 $n$ 天后可能的骆驼刺形状数量对 $276276276$ 取模后的结果。

Samples

3

2

4

8

Note

乘法的取模运算：$(a\times b) \bmod p = ((a\bmod p) \times (b\bmod p)) \bmod p$，为了确保答案正确尽量使用 long long 数据类型

Resources

电子科技大学第十三届 ACM 趣味程序设计竞赛