코딩이는 매일 매일 쿠키 반 개를 먹는다. 코딩이 친구 큐브는 코딩이에게 쿠키 N개 담긴 통을 선물로 주었다.
첫째 날에는 코딩이가 통에서 쿠키 한개를 꺼내어 반으로 쪼개서(쿠키의 크기는 모두 같고 정확하게 반으로 쪼개진다고 한다.)
한 조각은 맛있게 먹고, 다른 조각은 다시 다시 통에 넣는다.
다음 날 부터는 코딩이가 통에서 하나 꺼내는데 쿠키가 한 조각 일 수 도 있고, 이 전에 쪼개둔 반 조각 일 수도 있다고 한다.
반 조각이면 그 쿠키를 먹고, 아니라면 반을 쪼개서 한 조각은 먹고, 다른 조각은 다시 통에 넣는다.
코딩이는 먹은 기록을 남겨두기 위해서 메모장에 한 조각을 꺼낸 날에는 A를, 반 조각을 꺼낸 날에는 D를 적어 둔다.
총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이 때, 가능한 서로 다른 문자열의 개수는 총 몇개일까?