치환 수열의 구간 개수

처음에는 수 하나로 이루어진 수열이 있다. 매 초마다 수열의 모든 수가 동시에 다음 규칙에 따라 길이 3의 수열로 바뀐다.

• 1은 132로 바뀐다.
• 2는 211로 바뀐다.
• 3은 232로 바뀐다.

처음 수, 정수 N, 그리고 0부터 시작하는 인덱스 Left와 Right가 주어진다. N초 뒤의 수열에서 Left번째 수부터 Right번째 수까지에 포함된 1, 2, 3의 개수를 각각 구하라.

첫째 줄에 처음 수가 주어진다. 이 값은 1, 2, 3 중 하나이다.

둘째 줄에 Left, 셋째 줄에 Right, 넷째 줄에 N이 주어진다.

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

• 처음 수는 1, 2, 3 중 하나이다.
• 0 ≤ N ≤ 20
• 0 ≤ Left ≤ Right ≤ 3^N - 1
• Left와 Right는 모두 2,147,483,647보다 작다.