Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Constraints

* 1 \leq S \leq 2000
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


S


Output

Print the answer.

Examples

Input

7


Output

3


Input

2


Output

0


Input

1729


Output

294867501
import java.util.*;
import java.io.*;

public class Main  {
    static StringTokenizer st;
    static BufferedReader br;  
    static PrintWriter out;
 
    static HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); 
    static int[][] Factor;
    static long mod = (long)1e9 + 7;
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
       

        int S = nextInt();
        
        if(S<3){
            System.out.println(0);
            return;
        }

        int index = 1;
        for (int i=2; i<= S; i++) {
            if(isPrime(i)){
                map.put(index, i);
                index++;
            }
        } 

        Factor = new int[S+1][map.size()+1];

        for (int i=2; i<= S; i++) {
            int row = i;
            for (int j=1; j<= map.size(); j++) {
                int prime = map.get(j);
                while(row%prime==0){
                    row = row/prime;
                    Factor[i][j]++;
                }  
                if(row==1){
                    break;
                }
            } 
        } 


        int[] p = new int[S/3+1];

        long sum = 0;
        for (int x=1; x<p.length; x++) {
            int temp = S - 3*x;
            int bar = x - 1;
            sum += Combin(temp+bar,bar);
            sum %= mod;
        }

        System.out.println(sum);
       
    }
  
    public static long Combin(int a, int b) {
        if(b==0) return 1;

        long total = 1;
        int[] result = new int[map.size()+1];
        int loop = Math.min(b, a-b);

        for (int i=a; i>= a-loop+1; i--) {
            for (int j=1; j<= map.size(); j++) {
                result[j] += Factor[i][j];
            } 
        } 
        for (int i=loop; i>= 1; i--) {
            for (int j=1; j<= map.size(); j++) {
                result[j] -= Factor[i][j];
            } 
        } 

        for (int j=1; j<= map.size(); j++) {
            if(result[j]>0){
                for (int x=1; x<= result[j]; x++) {
                    total *= map.get(j);
                    total %= mod;
                }
            }
        } 

        return total;
    }

    public static boolean isPrime(int n) {  
        if (n <= 1) {  
            return false;  
        }  
        for (int i = 2; i <= Math.sqrt(n); i++) {  
            if (n % i == 0) {  
                return false;  
            }  
        }  
        return true;  
    }  

    public static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    public static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    static String next() throws IOException {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine().trim());
        return st.nextToken();
    }
}