多米诺骨牌（或简称多米诺）是大小为 $2 \times 1$ 的矩形骨牌。每个正方形包含一个 $1$ 到 $6$ 的数字。这些骨牌通常用于玩游戏，但在本题中，我们将它们用于不同的目的。

我们可以使用多米诺骨牌拼出宽度为 $W$、高度为 $3$ 的矩形。我们想知道有多少种可能的方法来拼接这样的矩形。

下图展示了拼接宽度为 $2$、高度为 $3$ 的矩形的三种可能方法。

如你所见，拼接矩形的方法有很多。例如，以下是宽度为 $12$ 的一种可能方案：

你的任务是编写一个程序，计算拼接宽度为 $W$、高度为 $3$ 的矩形的可能方法数。

输入格式

输入仅一行，包含一个整数 $W$，表示矩形的宽度。

$W$ 的值在 $1$ 到 $1000$ 之间。

输出格式

输出仅一行，包含一个整数，表示可能的方法数。由于数字可能很大，请输出答案模 $1000000007$ ($10^9 + 7$) 的结果。

样例

输入样例 1

2

输出样例 1

3

输入样例 2

8

输出样例 2

153

输入样例 3

30

输出样例 3

299303201

输入样例 4

3

输出样例 4

0

输入样例 5

56

输出样例 5

485646032

说明

在最后一个样例中，实际的结果是 $8155103542731753$，但我们必须输出它模 $10^9 + 7$ 后的结果。