骨牌铺方格

难度：T2 【知识点：多项递推】【知识点：分类计数】【知识点：初值】前置知识：循环、数组、初值与本节对应的递推关系。

题目描述

有一个 $1 \times n$ 的长方形方格条。你有数量足够的 $1 \times 1$ 、 $1 \times 2$ 和 $1 \times 3$ 骨牌，骨牌沿长条方向放置，不能重叠，也不能留空。

求铺满长条的不同方法数。从左到右的骨牌长度排列不同，视为不同方法；相同尺寸的骨牌不区分个体。

例如 $n=3$ 时，按从左到右的骨牌长度列出全部方法为 $1+1+1$ 、 $1+2$ 、 $2+1$ 、 $3$ ，共 $4$ 种。

输入一个整数 $n$ ，表示长条长度。

输出一个整数，表示不同铺法数。

$1 \le n \le 50$ 。答案需要使用 long long 保存。