小x住在左下角(0,0)处，小y在右上角(n,n)处。小x需要通过一段网格路才能到小y家。每次，小x可以选择下面任意一个方向前进：

右方：从(x,y)到点(x+1,y)；

上方：从(x,y)到点(x,y+1)；

右上方：从(x,y)到点(x+1,y+1)。

小x不想有连续的三步向同一个方向走。

问小x有多少种走法到达小y家。

输入格式

一行，一个整数n。1 ≤ n ≤ 500

输出格式

你的答案除以1 000 000 007的余数。