#D12005. 骨牌铺方格

骨牌铺方格

题目描述

有1×n1 \times n(n≤50n \le 50)的一个长方形,用1×11 \times 1、1×21 \times 2和1×31 \times 3的骨牌铺满方格,请问有多少种铺法?

例如当n=3n=3时为1×31 \times 3的方格。此时用1×11 \times 1、1×21 \times 2和1×31 \times 3的骨牌铺满方格,共有四种铺法。如下图:

输入描述

一个整数nn(n≤50n \le 50)

输出描述

骨牌的铺法。

样例

3
4