1. 

import java.util.Scanner;

/**
* Angewandte Mathematik, SS11
* Problem: 10229 Modular Fibonacci
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1170
*
* @author Benedikt Z¨nnchen
* @author Erik Wenzel
* @version 1.0, 12/04/2011
*
* Method : Matrixmultiplikation (LinAlg), int overflow
* Erkl¦rung: Da die Fibonaccizahlen Summen von sich selbst sind
* wiederholen sich die Modulo Ergebnisse. Bei 2^n je bei 2^n+ 2^(n-1).
* Beispiel f¾r 2^1:
* Fibs: 0 1 1 2 3 5 8 13 21
* mod2: 0 1 1 0 1 1 0 1 1 0 usw. => wiederholung bei alle 3 Schritte = 2^1+2^0!
* Da m<20 und 2^20+2^19 noch im Integerbereich liegt kann man bedenkenlos die Fibonaccizahlen,
* die nur im Integerbereich liegen nutzen. Kommt man ¾ber den Integerbereich f¦ngt man einfach
* wieder bei 0 an!
*
* Status : Accepted
* Runtime: 0.188
*/

public class Main
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int fibonacci;
while(sc.hasNextInt())
{
int n = sc.nextInt();
int m = sc.nextInt();

int mod = 1 << m;
fibonacci = matrixFibPow(n)[0][1];
/*
* Da Java kein unsigned int kennt muss man hier korrigieren um
* garantiert im positiven Integerbereich zu liegen.
*/

if(fibonacci<0)
{
fibonacci = fibonacci+Integer.MIN_VALUE;
}
System.out.println(fibonacci % mod);
}
}

/**
* Berechnet die n-te Potenz der Fibonacci Matrix duch Matrixmultiplikation
* @param power Potenz
* @return n-te Potenz der Fibonacci Matrix
*/
public static int[][] matrixFibPow(int power)
{

int[][] fib = new int[][] {{1, 1},
{1, 0}};
// F^0 = {{0,0}{0,0}}
if (power == 0)
{
return new int[2][2];
}
// F^1 = {{1,1}{1,0}}
else if (power == 1)
{
return fib;
}
// F^(2^n) = F^(2^(n-1)) * F^(2^(n-1))
else if (power % 2 == 0)
{
int[][] tmp = matrixFibPow(power / 2);
return matrixMul(tmp, tmp);
}
// F^n = F*F^(n-1)
else
{
return matrixMul(fib, matrixFibPow(power - 1));
}
}

/**
* Matrixmultiplikation einer 2x2 Matrix
* @param a linke Matrix
* @param b rechte Matrix
* @return
*/
public static int[][] matrixMul(int[][] a, int[][] b)
{
int[][] result = new int[2][2];

result[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
result[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
result[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
result[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];

//System.out.println("Current fib: " +result[0][1]);
return result;
}
}