1904번 01타일

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class main {
	static int[] dp;
    static StringTokenizer st;
	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       	
       	int n = Integer.parseInt(br.readLine());
       	
       	dp = new int[1000001];
       	
       	bw.write(w(n)+"\n");
       		
    	bw.flush();
    	bw.close();
    }
    
    static int w(int n) {
    	if(n==1) return 1;
    	if(n==2) return 2;
    	if(dp[n]!=0) return dp[n];
    	return dp[n]=(w(n-2)+w(n-1))%15746;
    }
}

역시 써보는게 최고,, 베이비 문제네,,