Time Limit: 1s
Memory Limit: 128MB
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 m ....
한가로운 초원에서 과제 걱정없이 풀을 뜯어먹고있는 소가 MooMoo 거리면서 노래를 부르고 있었다. 소의 노래는 굉장히 규칙성이 있었는데, 그의 노래 가사를 재귀적인 함수로 정의할 수 있다고 한다.
우선 S(0) 을 길이 3짜리 문자열인 "m o o" 라고 두자. 그 다음 S(k) 는 S(k-1) + "m o o ... o o" (o 가 k+2개) + S(k-1) 꼴로 정의가 가능하다. 즉
이 노래를 듣던 당신은 문득 소가 n번째로 말할 노래 가사가 궁금해졌다. n이 주어졌을 때, 소의 n번째 노래가사가 m인지 o인지 구해보자.
정수 n 하나가 주어진다. (1 ≤ n ≤ 10^9)
정답이 되는 m 또는 o를 출력한다.
11
m