/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
    public static BigInteger fooBI2(int n) {
        BigInteger[] vars = new BigInteger[3];
        vars[0] = BigInteger.valueOf(1L);
        vars[1] = BigInteger.valueOf(2L);
        vars[2] = BigInteger.valueOf(4L);
        for (int i = 3; i < n; i++) {
            vars[i%3] = vars[0].add(vars[1]).add(vars[2]);
        }
        return vars[(n-1)%3].mod(BigInteger.valueOf((long) (Math.pow(10, 9) + 7)));
    }

    public static int fooBI3(int n) {
    	int p = 1000000007;
        int[] vars = new int[3];
        vars[0] = 1;
        vars[1] = 2;
        vars[2] = 4;
        for (int i = 3; i < n; i++) {
            vars[i%3] = ((vars[0] + vars[1])%p +vars[2])%p;
        }
        return vars[(n-1)%3];
    }

	public static void main (String[] args) throws java.lang.Exception
	{
		System.out.println("15: " + fooBI2(15) + "  " + fooBI3(15));
		System.out.println("20000: " + fooBI2(20000) + "  " + fooBI3(20000));
	}
}