[백준 2749] 피보나치 수3

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
 
    private static final int PERIOD = 1500000;
    private static final int DIVIDE = 1000000;
 
    public static void main(String[] args) throws Exception, IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Long n = Long.parseLong(br.readLine());
    	System.out.println(fibonacci(n, PERIOD, DIVIDE));
    }
 
    public static int fibonacci(long number, int period, int divide) {
        if(number <= 1) return (int)number;
        int[] fibonaccis = new int[(int)(number % period) + 1];
        fibonaccis[1] = fibonaccis[2] = 1;
 
        for (int i = 3; i < fibonaccis.length; i++)
            fibonaccis[i] = (fibonaccis[i - 2] + fibonaccis[i - 1]) % divide;
 
        return fibonaccis[fibonaccis.length - 1];
    }
 
}