Problem: Haiku is a short form of Japanese poetry. A Haiku consists of three phrases with 5, 7 and 5 syllables, in this order.

Iroha is looking for X,Y,Z-Haiku (defined below) in integer sequences.

Consider all integer sequences of length N whose elements are between 1 and 10, inclusive. Out of those 10^N sequences, how many contain an X,Y,Z-Haiku?

Here, an integer sequence a_0, a_1, ..., a_{N-1} is said to contain an X,Y,Z-Haiku if and only if there exist four indices x, y, z, w (0 ≦ x < y < z < w ≦ N) such that all of the following are satisfied:

* a_x + a_{x+1} + ... + a_{y-1} = X
* a_y + a_{y+1} + ... + a_{z-1} = Y
* a_z + a_{z+1} + ... + a_{w-1} = Z



Since the answer can be extremely large, print the number modulo 10^9+7.

Constraints

* 3 ≦ N ≦ 40
* 1 ≦ X ≦ 5
* 1 ≦ Y ≦ 7
* 1 ≦ Z ≦ 5

Input

The input is given from Standard Input in the following format:


N X Y Z


Output

Print the number of the sequences that contain an X,Y,Z-Haiku, modulo 10^9+7.

Examples

Input

3 5 7 5


Output

1


Input

4 5 7 5


Output

34


Input

37 4 2 3


Output

863912418


Input

40 5 7 5


Output

562805100

Solution (in JAVA):

Solution:

import java.io.*;
import java.util.*;
import java.util.function.DoublePredicate;
import java.util.function.DoubleUnaryOperator;
 
public class Main{
	int mod = 1000000007;
	int X;
	int Y;
	int Z;
	int N;
	int[] sum;
	int[] pow10;
	int[][] dp;
	public void solve(){
		N = nextInt();
		X = nextInt();
		Y = nextInt();
		Z = nextInt();
		sum = new int[]{-1, X - 1, X + Y - 1, X + Y + Z - 1};
		dp = new int[N][1 << 18];
		for(int i = 0; i < N; i++){
			Arrays.fill(dp[i], -1);
		}
		
		pow10 = new int[N + 1];
		pow10[0] = 1;
		
		for(int i = 1; i < pow10.length; i++){
			pow10[i] = (int)((long)pow10[i - 1] * 10 % mod);
		}
		
		out.println(dfs(0, 0));
	}
	
	public int dfs(int n, int bit){
		String str = Integer.toBinaryString(bit);
		if(get(bit, 3, 0)){
			return pow10[N - n];
		}
		if(n == N){
			return 0;
		}
		if(dp[n][bit] != -1){
			return dp[n][bit];
		}
		int ans = 0;
		for(int i = 1; i <= 10; i++){
			int nb = 0;
			if(i <= X){
				nb = set(nb, 0, i);
			}
			for(int j = 1; j <= X; j++){
				if(get(bit, 0, j) && j + i <= X){
					nb = set(nb, 0, j + i);
				}
			}
			

			if(get(bit, 0, X) && i <= Y){
				nb = set(nb, 1, i);
			}
			
			for(int j = 1; j <= Y; j++){
				if(get(bit, 1, j) && j + i <= Y){
					nb = set(nb, 1, j + i);
				}
			}
			

			if(get(bit, 1, Y) && i <= Z){
				nb = set(nb, 2, i);
			}
			
			for(int j = 1; j <= Z; j++){
				if(get(bit, 2, j) && j + i <= Z){
					nb = set(nb, 2, j + i);
				}
			}
			ans = (ans + dfs(n + 1, nb)) % mod;
		}
		return dp[n][bit] = ans;
	}
	
	public boolean get(int bit, int t, int i){
		return (bit & 1 << (sum[t] + i)) != 0;
	}
	
	public int set(int bit, int t, int i){
		return bit | (1 << (sum[t] + i));
	}
	
	public int count(int num, int len){
		if(len == 1){
			if(0 < num && num <= 10){
				return 1;
			}else{
				return 0;
			}
		}
		if(num <= 0){
			return 0;
		}
		
		int ans = 0;
		for(int i = 1; i <= 10; i++){
			ans = (ans + count(num - i, len - 1)) % mod;
		}
		return ans;
	}
	
	private static PrintWriter out;
	public static void main(String[] args){
		out = new PrintWriter(System.out);
		new Main().solve();
		out.flush();
	}
	
	
	
	public static int nextInt(){
		int num = 0;
		String str = next();
		boolean minus = false;
		int i = 0;
		if(str.charAt(0) == '-'){
			minus = true;
			i++;
		}
		int len = str.length();
		for(;i < len; i++){
			char c = str.charAt(i);
			if(!('0' <= c && c <= '9')) throw new RuntimeException();
			num = num * 10 + (c - '0');
		}
		return minus ? -num : num;
	}
	
	public static long nextLong(){
		long num = 0;
		String str = next();
		boolean minus = false;
		int i = 0;
		if(str.charAt(0) == '-'){
			minus = true;
			i++;
		}
		int len = str.length();
		for(;i < len; i++){
			char c = str.charAt(i);
			if(!('0' <= c && c <= '9')) throw new RuntimeException();
			num = num * 10l + (c - '0');
		}
		return minus ? -num : num;
	}
	public static String next(){
		int c;
		while(!isAlNum(c = read())){}
		StringBuilder build = new StringBuilder();
		build.append((char)c);
		while(isAlNum(c = read())){
			build.append((char)c);
		}
		return build.toString();
	}
	
	
	private static byte[] inputBuffer = new byte[1024];
	private static int bufferLength = 0;
	private static int bufferIndex = 0;
	private static int read(){
		if(bufferLength < 0) throw new RuntimeException();
		if(bufferIndex >= bufferLength){
			try{
				bufferLength = System.in.read(inputBuffer);
				bufferIndex = 0;
			}catch(IOException e){
				throw new RuntimeException(e);
			}
			if(bufferLength <= 0) return (bufferLength = -1);
		}
		return inputBuffer[bufferIndex++];
	}
	
	private static boolean isAlNum(int c){
		return '!' <= c && c <= '~';
	}
}