4010 - 铺地面

有3种地砖,宽度都是1,长度为1、2、3这三种,用这三种地砖来铺一条宽度为1、长度为n的路面,问共有多少种不同的铺法?

例如铺宽度为1,长度为4的路面,共有7种不同的方法

Input

一个正整数n,3<n<30

Output

一个整数,表示方案数。

Examples

Input

4

Output

7
Time Limit 1 second
Memory Limit 128 MB
Discuss Stats
上一题 下一题