No submission language available for this problem.

Background

Special for beginners, ^_^

Description

现在有排成一行的 n(0 < n ≤ 50)个方格，用红、粉、绿三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色。求共有多少种满足要求的涂法。

Format

Input

输入一个整数 n(0 < n ≤ 50)，代表方格数。

Output

输出一个整数，代表共有多少种满足要求的涂法。

Samples

3

6

Limitation

1s, 1024KiB for each test case.