UVa 10229 - Modular Fibonacci

// UVa 10229 - Modular Fibonacci
// Fib(m+n) = Fib(m+1)*Fib(n) + Fib(m)*Fib(n-1)

#include <iostream>
#include <math.h>
#include <map>
using namespace std;

#define integer unsigned long long int

integer n, m;
map<integer, integer> memo;

integer mod(integer x) {
	return x % m;
}

integer fib(integer n) {
	if (n <= 1)
		return n;
	if (memo[n] != 0)
		return memo[n];
	integer sol = 0;
	if (n & 1) {
		integer Fn = fib(n >> 1);
		integer Fn1 = fib((n >> 1) + 1);
		sol = mod(mod(Fn * Fn) + mod(Fn1 * Fn1));
	} else {
		integer Fn = fib(n >> 1);
		integer Fn1 = fib((n >> 1) - 1);
		sol = mod(Fn * mod(Fn + mod(2 * Fn1)));
	}
	memo[n] = sol;
	return sol;
}

int main() {
	while (cin >> n >> m) {
		m = (1 << m);
		memo.clear();
		cout << fib(n) << endl;
	}
	return 0;
}