#10229Modular Fibonacci

★★★★

時間限制：2000 毫秒記憶體限制：64 MB

The Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...) are defined by the recurrence:

F₀ = 0
F₁ = 1
F_i = F_i-1 + F_i-2 for i > 1

Write a program which calculates M_n = F_n mod 2^m 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 M_n, one per line.

範例輸入 1

11 7
11 6

範例輸出 1

89
25

Pro 專屬功能：查看這題在歷屆 CPE 出現過幾次 — 升級以解鎖.