题目描述

二维离散世界有一种地形叫 New OIM（New OI Mountain）。这种山有若干个测试点，相邻两个测试点间只能用上升(‘/’) 或下降(‘\’) 来连接，而且 最左边 的测试点与地平线等高，海拔为 $0$ ，山上所有地方都可以低于地平线。

提示:

上升(‘/’) 意味着海拔 $+ 1$ 。下降(‘\’) 意味着海拔 $- 1$ 。

我们定义，一座 New OIM 的长度为他的测试点数量，一座 New OIM 的 完美值 为所有测试点海拔之和。

举个例子：

/\
  \

是一座长度为 $4$ 的 New OIM ，其完美值为 $0$ 。

\/

是一座长度为 $3$ 的 New OIM ，其完美值为 $-1$ 。

给定 New OIM 的长度 $n$ ，请你求出长度为 $n$ ，完美值为 $0$ 的 New OIM 的数量，请将结果对 $10^{13}+7$ 取模后输出。

输入格式

输入共一行，一个正整数 $n$ 。

输出共一行，表示长度为 $n$ ，完美值为 $0$ 的 New OIM 的数量，对 $10^{13}+7$ 取模。

9083333927634

【样例 1 解释】

两种方案中，测试点的海拔如下:

NO.1    0 1 0 -1
NO.2    0 -1 0 1

【数据范围】

对于所有测试数据保证： $1 \leq n \leq 300$ ， $n$ 除以 $4$ 的余数为 $0$ 或 $1$ 。