题目描述

有1×n的一个长方形，用用红、黄、蓝三色的骨牌（骨牌是1×1）铺满方格。要求任何相邻的方格不能同色，且首尾两格也不同色。求全部的满足要求的铺法总数。

输入格式

  一个整数n（1<=n<=30）。

输出格式

一个整数，表示铺法总数。

样例

input

1

output

3

提示

70%的数据，n<=25；
100%的数据，n<=30。