package Dynamic_programming;

import java.util.*;
public class beak_오르막수 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		//n이 1000까지면, 자리수가 1000...? 이건 배열로도 못만드는데....?
		
		int dp[][] = new int[n+1][10]; //0,1,2,3,4,5,6,7,8,9
		
		//한자리일때는, 자기자신보다 크거나 작은 수가 없으므로 1
		//따라서 한자리일때 계산은 dp[1][]층의 값을 전부 더하면 된다
		for(int i=0; i<10; i++)
			dp[1][i] = 1;
		
		for(int i=2; i<=n; i++) {//i층 =행
			for(int j=0; j<10; j++) {//j =열
				for(int k=0; k<=j; k++) {
					dp[i][j] += dp[i-1][k];
				}
				//나누기 필수
				dp[i][j] %= 10007;
			}
		}
		
		int sum = 0;
		for(int i=0; i<10; i++)
			sum += dp[n][i];
		
		System.out.println(sum);
		
	}//main
}

//참고 블로그
//https://fbtmdwhd33.tistory.com/74

import java.util.*;

class Solution {
	static public int[] solution(String s) {

        s = s.substring(1, s.length()-1);
        s += ",";
        
        String sp[] = s.split("},");

        for(int i=0; i<sp.length; i++)
        	sp[i] = sp[i].substring(1,sp[i].length());
        
        int cnt[] = new int[sp.length];
        
		StringTokenizer st = null;
		ArrayList<Integer>[] list = new ArrayList[sp.length];
		for(int i=0; i<list.length; i++) {
			list[i] = new ArrayList<>();
			st = new StringTokenizer(sp[i], ",");
			while(st.countTokens() > 0) {
				list[i].add(Integer.parseInt(st.nextToken()));
				cnt[i]++;
			}
		}
		
        
		int size = 1;
		int idx = 0;
		
		int num[] = new int[100000];
		
		LinkedList<Integer> ans = new LinkedList<>();
		
		while(size <=sp.length) {
			for(int i=0; i<list.length; i++) {
				if(list[i].size() == size) {
					idx = i;
					size++;
					break;
				}
			}
			
			for(int i=0; i<list[idx].size(); i++) {
				for(int j=0; j<list[idx].size(); j++) {
					int x = list[idx].get(j);
					
					if(num[x] ==0) {
						ans.add(x);
						num[x] = 1;
					}	
				}
			}
		}
		
        return ans.stream().mapToInt(i->i).toArray();
    }
}

package String;

import java.util.*;

public class prog_2_뉴스클러스터링 {

    static public int solution(String str1, String str2) {
        str1 = str1.toLowerCase();	str2 = str2.toLowerCase();
        
        String con = "abcdefghijklmnopqrstuvwxyz";
        
        String s1  = str1;
        String s2  = str2;
        
        LinkedList<String> l1 = new LinkedList<>();
        LinkedList<String> l2 = new LinkedList<>();
        
        for(int i=0; i<s1.length()-1; i++) {
        	if(con.contains(String.valueOf(s1.charAt(i))) && con.contains(String.valueOf(s1.charAt(i+1))))
        			l1.add(s1.substring(i,i+2));
        }
        
        for(int i=0; i<s2.length()-1; i++) {
        	if(con.contains(String.valueOf(s2.charAt(i))) && con.contains(String.valueOf(s2.charAt(i+1))))
        			l2.add(s2.substring(i,i+2));
        }
        
        boolean a1[] = new boolean[l1.size()];
        boolean a2[] = new boolean[l2.size()];
        
        int in = 0;
        
        for(int i=0; i<l1.size(); i++) {
        	for(int j=0; j<l2.size(); j++) {
        		if(!a1[i] && !a2[j]) {
	        		if(l1.get(i).equals( l2.get(j))) {
	        			a1[i] = a2[j] = true;
	        			in++;
	        			break;
	        		}
        		}
        	}
        }
   
        //0을 나누는 오류 생기지 않게 /out 해주기전에 return 해준다
        if(l1.isEmpty() && l2.isEmpty())
        	return 65536;        
        
        int out = a1.length + a2.length -in;
        
        int answer = (in*65536/out);
        return answer;
    }
    
    public static void main(String[] args) {
		
    	System.out.println(solution("aa1+aa2", "AAAA12"));
    	
	}
}

package DP;

public class prog_멀리뛰기_re {

	static public long solution(int n) {
		
		long dp[] = new long[2001];
		
		dp[1] = 1;
		dp[2] = 2;
		
		for(int i=3; i<=n; i++) {
			dp[i] = (dp[i-1] + dp[i-2]) %1234567;
		}
		
		return dp[n];
	}
}

package Dfs_Bfs;

import java.util.*;

//15min
public class beak_바이러스 {
	static int maze[][];
	
	static public void dfs(int x, int visited[]) {
		visited[x] = 1;
		
		for(int i=0; i<maze.length; i++) {
			if(maze[i][0] == x && visited[maze[i][1]] == 0) {
				dfs(maze[i][1], visited);
			}
			
			if(maze[i][1] == x && visited[maze[i][0]] == 0) {
				dfs(maze[i][0], visited);
			}
		}
		
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		int visited[] = new int[n+1];
		
		maze = new int[m][2];

		for(int i=0; i<m; i++) {
			maze[i][0] = sc.nextInt();
			maze[i][1] = sc.nextInt();
		}
		
		for(int i=0; i<maze.length; i++) {
			if(maze[i][0] == 1) {
				visited[maze[i][0]] = 1;//visited
				dfs(maze[i][1], visited);
			}
			
			if(maze[i][1] == 1) {
				visited[maze[i][1]] = 1;//visited
				dfs(maze[i][0], visited);
			}
				
		}
		
		int answer = 0;
		for(int i=2; i<visited.length; i++) {
			if(visited[i] == 1)
				answer++;
		}
		
		System.out.println(answer);
	}
}