U546616 骨牌

有 $1 \times n$ 的一个长方形，用一个 $1 \times 1$ 、$1 \times 2$ 和 $1 \times 3$ 的骨牌铺满方格，请问有多少种铺法？ 例如 当 $ n = 3 $时为 $1 \times 3$ 的方格。 此时用 $1 \times 1$ 、$1 \times 2$ 和 $1 \times 3$ 的骨牌铺满方格，共有四种铺法。如下图： 

一个整数 $n$。

骨牌的铺法对 $10 ^ 9 + 7$ 取模。

对于 $50 \%$ 的数据范围， $n \le 500$; 对于 $100 \%$ 的数据范围，$n \le 10 ^ {18}$。