Competitions

# Forbidden Strings

A string of letters A, B, C is forbidden if there are three consecutive letters from which one is A, one is B and one is C. For example, BAACAACCBAAA is forbidden, while AABBCCAABB is not.

How many such strings of length n are not forbidden?

#### Input

Each line contains one number n (1n30).

#### Output

For each input value of n print in a separate line the number of strings of length n are not forbidden.

Time limit 1 second
Memory limit 128 MiB
Input example #1
2
3
4

Output example #1
9
21
51