RETO11F - Fibonacci

no tags 

Los números de Fibonacci (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...) están definidos por la recurrencia:

 

F0 = 0

F1 = 1

Fi = F(i-1) + F(i-2)  para i> 1

 

Escriba un programa que calcule Mn = Fn MOD 2m para un par dado de n y m.

0 < n  < 2147483647 y 0 ≤ m <20. Tenga en cuenta que a mod b es el residuo de dividir a por b.

Input

La entrada consiste en varias líneas que especifican un par de n y m. 

Output

La salida debe ser el correspondiente Mn, uno por línea.

Example

Input:

11 7

11 6

Output:

  89

  25



Added by:MaratónAFDM
Date:2017-10-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C CSHARP C++ 4.3.2 JAVA NODEJS PHP PYTHON VB.NET