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 consists of several lines specifying a pair of n and m.
Output should be corresponding Mn, one per line.
範例輸入 1
11 7 11 6
範例輸出 1
89 25
Pro 專屬功能： 查看這題在歷屆 CPE 出現過幾次 — 升級以解鎖.