최근 충근이는 "Moo" 게임에 빠져있다. 이 게임은 "Moo" 문자열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다.
"Moo" 문자열은 길이가 무한대이며, 다음과 같이 구성되어 있다.
m o o m o o o m o o m o o o o m o o m o o o m o o m o o o o o ....
"Moo" 문자열은 다음과 같은 방법으로 재귀적으로 만들 수 있다. 먼저, S(0)을 길이가 3인 문자열 "m o o"이라고 하자. 1보다 크거나 같은 모든 k에 대해서, S(k)는 S(k-1)과 o가 k+2개인 문자열 "m o ... o" 와 S(k-1)을 합쳐서 만들 수 있다.
S(0) = "m o o"
S(1) = "m o o m o o o m o o"
S(2) = "m o o m o o o m o o m o o o o m o o m o o o m o o"
위와 같은 식으로 만들면, 길이가 무한대인 문자열을 만들 수 있으며, 이것을 "Moo" 문자열이라고 한다.
N이 주어졌을 때, "Moo" 문자열의 N번째 글자를 구하는 프로그램을 작성하시오.