Problems
금지된 문자열이 존재하지 않는 모든 A와 B, 그리고 C로 이뤄진 길이가 N인 문자열의 수를 출력하는 프로그램을 작성하라.
금지된 문자열이란 문자열에서 "ABC", "ACB", "BAC", "BCA", "CAB", "CBA" 와 같은 부분문자열(substring)이 존재하는 문자열이다.
예를 들어 "BAACAACCBAAA"은 금지된 문자열이나, "AABBCCAABB"는 그렇지 않다.
Input
입력은 1이상 30이하의 정수 N이 입력된다.
Output
길이 N의 올바른 문자열의 수를 출력한다. 주의 : 답이 32-bit integer 범위를 넘어갈 수 있음을 유의한다.
Example
2
9
Hint
You must sign in to write code.