10299 Problem A: Modular Fibonacci（斐波那契的矩阵快速幂）

10299 Problem A: Modular Fibonacci（斐波那契的矩阵快速幂）2014-04-20 csdn博客 accelerator_Problem A: Modular Fibonacci

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 for i>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 and Output

Input consists of several lines specifying a pair of n and m. Output should be corresponding Mn, one per line.

Sample Input

11 7

11 6

Sample Output