The Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...) are defined by the recurrence: F0 = 0 F1 = 1 Fi = Fi−1+Fi−2 fori>1 Write a program which calculates Mn = Fn mod 2m for given pair of n and m. 0 ≤ n ≤ 2147483647 and 0 ≤ m < 20. Note that a mod b gives the remainder when a is divided by b. Input Input consists of several lines specifying a pair of n and m. Output Output should be corresponding Mn, one per line. Sample Input 11 7 11 6 Sample Output 89 25