1588번 - 수열

세준이는 가장 처음에 수 하나만 가지고 있는 수열을 가지고 있다. 매 초마다 1은 132로 바뀌고, 2는 211로 바뀌고, 3은 232로 바뀐다. 이런 변환은 매 초마다 동시에 일어난다. N초 후에 Left번째 수부터 Right번째 수 중에 1의 개수, 2의 개수, 3의 개수를 구하는 프로그램을 작성하시오. (Left와 Right를 셀 때, 가장 처음 수를 0번째 수, 그 다음 수를 1번째 수로 센다.)

예를 들어, 가장 처음 수가 1고, N=2이고, Left = 2, Right = 6이라고 하면, 2초 후에는 132232211이 될 것이다. 따라서 Left부터 Right까지 부분 수열은 22322이다. 따라서, 1의 개수는 0, 2의 개수는 4, 3의 개수는 1이다.

첫째 줄에 가장 처음에 들어있던 수가 주어진다. 이 수는 1, 2, 3중에 하나다. 둘째 줄에는 Left가 주어지고, 셋째 줄에는 Right, 넷째 줄에는 N이 주어진다.

N은 0보다 크거나 같고, 20보다 작거나 같은 자연수이고, Right는 0보다 크거나 같으며, 3^N-1보다 작거나 같다. Left는 0보다 크거나 같고, Right보다 작거나 같고, Left와 Right는 모두 2147483647보다 작거나 같다.

첫째 줄에 1의 개수, 2의 개수, 3의 개수를 공백으로 구분하여 출력한다.

• 0 ≤ N ≤ 20
• 0 ≤ Left ≤ Right ≤ min(2,147,483,647, 3^N-1)