public class PowTest {

	public int pow(int a, int n) {
		if(n == 0)
			return 1;
		if(n == 1)
			return a;
		if(n % 2 == 0) {
			int temp = pow(a, n/2);
			return temp * temp;
		}
		else {
			int temp = pow(a,(n-1)/2);
			return temp * temp * a;
		}
	}
	
	public int[] matrixPow(int[] a, int n) {
		
		int[] res = null;
		int[] temp = a;
		while(n > 0) {
			if((n & 1) == 1) {
				if(res == null)
					res = temp;
				else {
					res = matrixMult(res,2,2,temp,2,2);
				}
			}
			temp = matrixMult(temp,2,2,temp,2,2);
			n = n >> 1;
		}
		return res;
	}
	
	public int fibonacci(int n) {
		if(n < 2)
			return n;
		int[] a = {1,1,1,0};
		int[] power = matrixPow(a, n-1);
		int[] b = {1,0};
		int[] res = matrixMult(power, 2, 2, b, 2, 1);
		return res[0];
	}
	
	public int[] matrixMult(int[] a, int aRows, int aCuls, int[] b, int bRows, int bCuls) {
		int[] res = new int[aRows * bCuls];
		for(int i = 0; i < res.length; i++) {
			int resRow = i / bCuls;
			int resCul = i % bCuls;
			int temp = 0;
			for(int j = 0; j < aCuls; j++) {
				temp += a[j + resRow * aCuls] * b[resCul + j * bCuls ];
			}
			res[i] = temp;
		}
		return res;
	}
	
	
	public static void main(String[] args) {
		PowTest powTest = new PowTest();
		System.out.println(powTest.fibonacci(5));

//		System.out.format("%x", -1);
//		int n = -1;
//		int count = 0;
//		while(n != 0) {
//			n = (n - 1) & n;
//			count++;
//		}
//		System.out.println(count);
	}
}