Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Problem hidden

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