UVa10229 - Modular Fibonacci

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

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

Sample Input

11 7
11 6

Sample Output

89
25

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; vector
         
           fib[21]; void init(){ for(int i = 1; i <= 20; i++){ int mod = 1<
          
           > n >> m){ if(m==0) cout<<0<