问题描述

现在有排成一行的n个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求出共有多少种满足要求的涂法。(若是1个格子只作为首格子)

输入格式:

输入一个整数n，表示n个格子

输出格式:

输出一个整数x，表示有x种满足要求的涂法

3

6

4

18

数据范围

0< n <=50