Fibonacci-like sequences P68314


Statement
 

pdf   zip

thehtml

Inspired by the Fibonacci sequence F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2   for   n ≥ 2, Xavier defined his own sequence of numbers:

X0 = 0, X1 = 1, Xn = XXn−1 + XXn−2   for   n ≥ 2 .

Max also wanted his own sequence of numbers, so he modified Xavier’s definition a bit:

M0 = 1, M1 = 0, Mn = MMn−1 + MMn−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 109.

Output

For each case, print Xn or Mn depending on c.

Public test cases
  • 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
    
  • Information
    Author
    Félix Moreno
    Language
    English
    Official solutions
    C++
    User solutions
    C++