1
2

3
8

分析：這是一道遞推題，但是比一般的遞推要復雜一點兒，需要考慮兩種情況。

1、可以由 n - 1 個字符後面再加一個得到 n 個字符的情況，但是需要考慮 n - 1 個字符的最後一個字符是不是 O .

2、使用一個二維數組 nums [ n ][ 2 ] ，存儲 n 個字符的情況。其中，nums [ n ][ 0 ] 存儲最後一個字符是 O 的情況，nums [ n ][ 1 ]存儲最後一個字符不是 O 的情況。

3、如果在 n - 1 個字符的後面加 O ，則 n - 1 個字符的最後一個字符不能是 O ，所以：nums [ n ][ 0 ] = nums [ n - 1 ][ 1 ] * 1

4、如果在 n - 1 個字符的後面加非 O 字符（E、F），則 n - 1 個字符的最後一個字符沒有限制，所以：nums [ n ][ 1 ] = ( nums [ n - 1 ][ 0 ] + nums [ n - 1 ][ 1 ] ) * 2

import java.util.Scanner;

public class Main {

	static long[][] nums = new long[40][2];

	static {
		nums[1][0] = 1;
		nums[1][1] = 2;
		for (int i = 2; i < 40; i++) {
			nums[i][0] = nums[i - 1][1];
			nums[i][1] = 2 * (nums[i - 1][0] + nums[i - 1][1]);
		}
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		while (scanner.hasNext()) {
			int n = scanner.nextInt();

			System.out.println(nums[n][0] + nums[n][1]);
		}
	}
}