g6-07872. 铺砖 未做

有一个 $2\times n$ 的格子，用 $1\times 2$ 和 $2\times 1$ 的砖铺满，一共有多少种不同的铺法？答案对 $10^9+7$ 取模。

一行一个整数 $n$。

一行一个整数，表示铺法数对 $10^9+7$ 取模的结果。

输入 1

4

输出 1

5

对于所有数据，$0\le n\le 10^6$。