Inspired by the Fibonacci sequence F_{0} = 0, F_{1} = 1, F_{n} = F_{n−1} + F_{n−2} for n ≥ 2, Xavier defined his own sequence of numbers:
X_{0} = 0, X_{1} = 1, X_{n} = X_{Xn−1} + X_{Xn−2} for n ≥ 2 . |
Max also wanted his own sequence of numbers, so he modified Xavier’s definition a bit:
M_{0} = 1, M_{1} = 0, M_{n} = M_{Mn−1} + M_{Mn−2} for n ≥ 2 . |
Can you compute the n-th term of any of these two new sequences?
Input
Input consists of several cases, each with a character c, which is ‘X’ or ‘M’, and a natural n between 0 and 10^{9}.
Output
For each case, print X_{n} or M_{n} depending on c.
Input
X 0 X 1 X 2 X 3 M 0 M 1 M 2 M 3
Output
0 1 1 2 1 0 1 1