Problem 1789. -- 骨牌铺法

1789: 骨牌铺法

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 1520  Accepted: 723
[Submit][Status][Web Board]

Description

有1×n的一个长方形,用一个1×1、1×2和1×3的骨牌铺满方格。例如当n=3时为1×3的方格。此时用1×1、1×2和1×3的骨牌铺满方格,共有四种铺法。

Input

包含多组测试数据。每组测试数据包含一个正整数。

Output

每组测试数据输出一个整数,占一行。

Sample Input

3

Sample Output

4

Source

[Submit][Status][Web Board]