피보나치 공식

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());
        if (n == 0) {
            System.out.println(0);
            return;
        }
        //저번에 푼거 6에선가 푼건데
        //0 1 1 2 3 5 8 13 21
        long[][] A = {
                {1, 1},
                {1, 0}
        };
        long[][] result = power(A, n - 1);
        System.out.println(result[0][0] % 1000000);
    }
 
    private static long[][] power(long[][] A, long n) {
        long[][] result = {
                {1, 0},
                {0, 1}
        };
        while (n > 0) {
            if (n % 2 == 1) {//홀수면 일단 지수를 하나 줄이기위한 작업을 먼저 한다. 단위 행렬이랑 A행렬 곱하면 지수가 하나 빠지는 원리
                result = multiply(result, A);
            }
            A = multiply(A, A);
            n /= 2;
        }
        return result;
    }
 
    private static long[][] multiply(long[][] A, long[][] B) {
        long[][] C = new long[2][2];
        C[0][0] = ((A[0][0] * B[0][0]) % 1000000 + (A[0][1] * B[1][0]) % 1000000) % 1000000;
        C[0][1] = (A[0][0] * B[0][1] % 1000000 + A[0][1] * B[1][1] % 1000000) % 1000000;
        C[1][0] = (A[1][0] * B[0][0] % 1000000 + A[1][1] * B[1][0] % 1000000) % 1000000;
        C[1][1] = (A[1][0] * B[0][1] % 1000000 + A[1][1] * B[1][1] % 1000000) % 1000000;
        return C;
    }
}