정올이는 N개의 발판을 바닥에 배치하여 태극권 훈련을 하는 중이다. 각 발판은 N-1개의 선으로 연결되어 있는데, 이 선은 검은색 혹은 흰색으로 이루어져 있다.

태극권은 끊어지지 않고 이어지는 특성을 가지고 있기에 모든 발판은 다른 모든 발판으로 나아갈 수 있는 경로가 존재한다.

정올이는 오늘 태극권의 걷는 방식 중 하나인 태극보법을 훈련하려고 한다. 방법은 단순하다.

하나의 발판 A에서 시작하여 한 번 밟은 발판들을 중복하여 밟지 않으며 A와 다른 발판 B로 걸음을 이어나가는 것이다.

다만 음과 양의 어우러짐은 태극의 이치이기에 경로 상의 검은색과 흰색의 수가 같아야 한다.

만약 너무 경로가 너무 길면 힘들수가 있기에 발판 A와 B 사이에 쉴 수 있는 발판이 있어야 한다. 이때, 중간 발판에서 쉬기 위해서는 해당 발판까지의 경로 상의 검은색과 흰색의 수가 동일해야 한다.

정올이는 가능한 모든 경로에 대하여 태극보법을 훈련하고자 한다.

발판의 수와 각 발판이 어떻게 연결되어 있는지가 주어졌을 때, 총 몇 가지 경로의 훈련을 해야하는지 출력하는 프로그램을 작성하시오.

태극권 timer 2초 memory 128MB

태극권 2초 128MB