0과 1로 이루어진 이진 문자열 0101101은 0과 1의 개수의 차이가 1 이하이다. 뿐만 아니라, 첫 번째 문자를 포함하는 모든 부분 문자열 0, 01, 010, 0101, 01011, 010110, 0101101 모두 0과 1의 개수의 차이가 1 이하이다.

이와 같이, 이진 문자열 중에서 첫 번째 문자를 포함하는 모든 부분 문자열의 0과 1의 개수의 차이가 1이하인 문자열을 균형잡힌 문자열이라 부른다. 문자열 자체도 자신의 부분 문자열이다.

양의 정수 n 이 주어질 때, 길이가 n 인 이진 문자열 중에서 균형잡힌 문자열의 수를 구하는 프로그램을 작성하시오.

예를 들어, n = 3인 경우에는 010, 011, 100, 101 네 개의 문자열이 균형잡힌 문자열이다.

균형잡힌 문자열 timer 1s memory 512MB

균형잡힌 문자열 1s 512MB