import java.math.BigInteger;

public class Main {
	// матричное умножение двух матриц размера 2 на 2
	public static BigInteger[][] matrixMultiplication(BigInteger[][] a, BigInteger[][] b) {
		// [a00 * b00 + a01 * b10, a00 * b01 + a01 * b11]
		// [a10 * b00 + a11 * b10, a10 * b01 + a11 * b11]
		return new BigInteger[][]{
				{
						a[0][0].multiply(b[0][0]).add(a[0][1].multiply(b[1][0])),
						a[0][0].multiply(b[0][1]).add(a[0][1].multiply(b[1][1]))
				},
				{
						a[1][0].multiply(b[0][0]).add(a[1][1].multiply(b[1][0])),
						a[1][0].multiply(b[0][1]).add(a[1][1].multiply(b[1][1]))
				},
		};
	}

	// возведение матрицы размера 2 на 2 в степень n
	public static BigInteger[][] matrixPowerFast(BigInteger[][] a, int n) {
		if (n == 0) {
			// любая матрица в нулевой степени равна единичной матрице
			return new BigInteger[][]{
					{BigInteger.ONE, BigInteger.ZERO},
					{BigInteger.ZERO, BigInteger.ONE}
			};
		} else if (n % 2 == 0) {
			// a ^ (2k) = (a ^ 2) ^ k
			return matrixPowerFast(matrixMultiplication(a, a), n / 2);
		} else {
			// a ^ (2k + 1) = (a) * (a ^ 2k)
			return matrixMultiplication(matrixPowerFast(a, n - 1), a);
		}
	}

	// функция, возвращающая n-ое число Фибоначчи
	public static BigInteger fibonacci(int n) {
		if (n == 0) {
			return BigInteger.ZERO;
		}

		BigInteger[][] a = {
				{BigInteger.ONE, BigInteger.ONE},
				{BigInteger.ONE, BigInteger.ZERO}
		};
		BigInteger[][] powerOfA = matrixPowerFast(a, n - 1);
		// nthFibonacci = powerOfA[0][0] * F_1 + powerOfA[0][0] * F_0 = powerOfA[0][0] * 1 + powerOfA[0][0] * 0
		BigInteger nthFibonacci = powerOfA[0][0];
		return nthFibonacci;
	}

	public static void main(String[] args) {
		System.out.println(fibonacci(1024));
	}
}

aW1wb3J0IGphdmEubWF0aC5CaWdJbnRlZ2VyOwoKcHVibGljIGNsYXNzIE1haW4gewoJLy8g0LzQsNGC0YDQuNGH0L3QvtC1INGD0LzQvdC+0LbQtdC90LjQtSDQtNCy0YPRhSDQvNCw0YLRgNC40YYg0YDQsNC30LzQtdGA0LAgMiDQvdCwIDIKCXB1YmxpYyBzdGF0aWMgQmlnSW50ZWdlcltdW10gbWF0cml4TXVsdGlwbGljYXRpb24oQmlnSW50ZWdlcltdW10gYSwgQmlnSW50ZWdlcltdW10gYikgewoJCS8vIFthMDAgKiBiMDAgKyBhMDEgKiBiMTAsIGEwMCAqIGIwMSArIGEwMSAqIGIxMV0KCQkvLyBbYTEwICogYjAwICsgYTExICogYjEwLCBhMTAgKiBiMDEgKyBhMTEgKiBiMTFdCgkJcmV0dXJuIG5ldyBCaWdJbnRlZ2VyW11bXXsKCQkJCXsKCQkJCQkJYVswXVswXS5tdWx0aXBseShiWzBdWzBdKS5hZGQoYVswXVsxXS5tdWx0aXBseShiWzFdWzBdKSksCgkJCQkJCWFbMF1bMF0ubXVsdGlwbHkoYlswXVsxXSkuYWRkKGFbMF1bMV0ubXVsdGlwbHkoYlsxXVsxXSkpCgkJCQl9LAoJCQkJewoJCQkJCQlhWzFdWzBdLm11bHRpcGx5KGJbMF1bMF0pLmFkZChhWzFdWzFdLm11bHRpcGx5KGJbMV1bMF0pKSwKCQkJCQkJYVsxXVswXS5tdWx0aXBseShiWzBdWzFdKS5hZGQoYVsxXVsxXS5tdWx0aXBseShiWzFdWzFdKSkKCQkJCX0sCgkJfTsKCX0KCgkvLyDQstC+0LfQstC10LTQtdC90LjQtSDQvNCw0YLRgNC40YbRiyDRgNCw0LfQvNC10YDQsCAyINC90LAgMiDQsiDRgdGC0LXQv9C10L3RjCBuCglwdWJsaWMgc3RhdGljIEJpZ0ludGVnZXJbXVtdIG1hdHJpeFBvd2VyRmFzdChCaWdJbnRlZ2VyW11bXSBhLCBpbnQgbikgewoJCWlmIChuID09IDApIHsKCQkJLy8g0LvRjtCx0LDRjyDQvNCw0YLRgNC40YbQsCDQsiDQvdGD0LvQtdCy0L7QuSDRgdGC0LXQv9C10L3QuCDRgNCw0LLQvdCwINC10LTQuNC90LjRh9C90L7QuSDQvNCw0YLRgNC40YbQtQoJCQlyZXR1cm4gbmV3IEJpZ0ludGVnZXJbXVtdewoJCQkJCXtCaWdJbnRlZ2VyLk9ORSwgQmlnSW50ZWdlci5aRVJPfSwKCQkJCQl7QmlnSW50ZWdlci5aRVJPLCBCaWdJbnRlZ2VyLk9ORX0KCQkJfTsKCQl9IGVsc2UgaWYgKG4gJSAyID09IDApIHsKCQkJLy8gYSBeICgyaykgPSAoYSBeIDIpIF4gawoJCQlyZXR1cm4gbWF0cml4UG93ZXJGYXN0KG1hdHJpeE11bHRpcGxpY2F0aW9uKGEsIGEpLCBuIC8gMik7CgkJfSBlbHNlIHsKCQkJLy8gYSBeICgyayArIDEpID0gKGEpICogKGEgXiAyaykKCQkJcmV0dXJuIG1hdHJpeE11bHRpcGxpY2F0aW9uKG1hdHJpeFBvd2VyRmFzdChhLCBuIC0gMSksIGEpOwoJCX0KCX0KCgkvLyDRhNGD0L3QutGG0LjRjywg0LLQvtC30LLRgNCw0YnQsNGO0YnQsNGPIG4t0L7QtSDRh9C40YHQu9C+INCk0LjQsdC+0L3QsNGH0YfQuAoJcHVibGljIHN0YXRpYyBCaWdJbnRlZ2VyIGZpYm9uYWNjaShpbnQgbikgewoJCWlmIChuID09IDApIHsKCQkJcmV0dXJuIEJpZ0ludGVnZXIuWkVSTzsKCQl9CgoJCUJpZ0ludGVnZXJbXVtdIGEgPSB7CgkJCQl7QmlnSW50ZWdlci5PTkUsIEJpZ0ludGVnZXIuT05FfSwKCQkJCXtCaWdJbnRlZ2VyLk9ORSwgQmlnSW50ZWdlci5aRVJPfQoJCX07CgkJQmlnSW50ZWdlcltdW10gcG93ZXJPZkEgPSBtYXRyaXhQb3dlckZhc3QoYSwgbiAtIDEpOwoJCS8vIG50aEZpYm9uYWNjaSA9IHBvd2VyT2ZBWzBdWzBdICogRl8xICsgcG93ZXJPZkFbMF1bMF0gKiBGXzAgPSBwb3dlck9mQVswXVswXSAqIDEgKyBwb3dlck9mQVswXVswXSAqIDAKCQlCaWdJbnRlZ2VyIG50aEZpYm9uYWNjaSA9IHBvd2VyT2ZBWzBdWzBdOwoJCXJldHVybiBudGhGaWJvbmFjY2k7Cgl9CgoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewoJCVN5c3RlbS5vdXQucHJpbnRsbihmaWJvbmFjY2koMTAyNCkpOwoJfQp9