Problem E: Counting

The Problem

Gustavo knows how to count, but he is now learning how write numbers. As he is a very good student, he already learned 1, 2, 3 and 4. But he didn't realize yet that 4 is different than 1, so he thinks that 4 is another way to write 1. Besides that, he is having fun with a little game he created himself: he make numbers (with those four digits) and sum their values. For instance:

132 = 1 + 3 + 2 = 6
112314 = 1 + 1 + 2 + 3 + 1 + 1 = 9 (remember that Gustavo thinks that 4 = 1)

The Input

Input will consist on an arbitrary number of sets. Each set will consist on an integer n such that 1 <= n <= 1000. You must read until you reach the end of file.

The Output

For each number read, you must output another number (on a line alone) stating how much numbers Gustavo can make such that the sum of their digits is equal to the given number.

Sample Input

2
3

Sample Output

5
13

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		BigInteger[] dp = new BigInteger[1001];
		dp[0] = new BigInteger("1");
		for(int i = 1; i <= 1000; i++) {
			dp[i] = new BigInteger("0");
			if(i-1 >= 0) {
				dp[i] = dp[i].add(dp[i-1]);
				dp[i] = dp[i].add(dp[i-1]);
			}
			if(i-2 >= 0)
				dp[i] = dp[i].add(dp[i-2]);
			if(i-3 >= 0)
				dp[i] = dp[i].add(dp[i-3]);
		}
		while(cin.hasNextInt()) {
			int n = cin.nextInt();
			System.out.println(dp[n].toString());
		}
	}
}