Furik loves writing all sorts of problems, especially such that he can't solve himself. You've got one of his problems, the one Furik gave to Rubik. And Rubik asks you to solve it.

There is integer n and array a, consisting of ten integers, indexed by numbers from 0 to 9. Your task is to count the number of positive integers with the following properties:

  * the number's length does not exceed n; 
  * the number doesn't have leading zeroes; 
  * digit i (0 ≤ i ≤ 9) occurs in the number at least a[i] times. 

Input

The first line contains integer n (1 ≤ n ≤ 100). The next line contains 10 integers a[0], a[1], ..., a[9] (0 ≤ a[i] ≤ 100) — elements of array a. The numbers are separated by spaces.

Output

On a single line print the remainder of dividing the answer to the problem by 1000000007 (109 + 7).

Examples

Input

1
0 0 0 0 0 0 0 0 0 1


Output

1


Input

2
1 1 0 0 0 0 0 0 0 0


Output

1


Input

3
1 1 0 0 0 0 0 0 0 0


Output

36

Note

In the first sample number 9 meets the requirements.

In the second sample number 10 meets the requirements.

In the third sample numbers 10, 110, 210, 120, 103 meet the requirements. There are other suitable numbers, 36 in total.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Enumeration;
import java.util.Iterator;
import java.util.Properties;

/**
 * Works good for CF
 * 
 * @author cykeltillsalu
 */
public class MyB131 {

	// some local config
	static boolean test = false;
	static String testDataFile = "testdata.txt";
	static String feedFile = "feed.txt";
	CompetitionType type = CompetitionType.CF;
	private static String ENDL = "\n";

	// solution
	private void solve() throws Throwable {
		int n = iread();
		int[][] bin = new int[n][n];
		bin[0][0] = 1;
		int mod = 1000000007;
		for (int i = 1; i < n; i++) {
			bin[i][0] = 1;
			for (int j = 1; j < n; j++) {
				bin[i][j] = (bin[i-1][j] + bin[i-1][j-1]) % mod;
			}
		}
		
		int[] a = new int[10];
		for (int i = 0; i < 10; i++) {
			a[i] = iread();
		}
		
		long res = 0;
		for (int startDigit = 1; startDigit < 10; startDigit++) {
			int[] minDigits = a.clone();
			minDigits[startDigit] = Math.max(minDigits[startDigit]-1, 0);
			int[] ways = new int[n];
			ways[0] = 1;
			
			for (int digit = 0; digit < 10; digit++) {
				int[] nways = new int[n];
				for (int prevLength = 0; prevLength < n; prevLength++) {
					if(ways[prevLength] == 0){
						continue;
					}
					for (int curCnt = minDigits[digit]; curCnt  + prevLength < n; curCnt++) {
						nways[curCnt + prevLength] = (int) ((nways[prevLength + curCnt] + ways[prevLength] * (long)bin[curCnt + prevLength][curCnt]) % mod);
					}
				}
				ways = nways;
			}
			for (int i : ways) {
				res = (res + i) % mod;
			}
		}
		
		System.out.println(res);
	}

	public int iread() throws Exception {
		return Integer.parseInt(wread());
	}

	public double dread() throws Exception {
		return Double.parseDouble(wread());
	}

	public long lread() throws Exception {
		return Long.parseLong(wread());
	}

	public String wread() throws IOException {
		StringBuilder b = new StringBuilder();
		int c;
		c = in.read();
		while (c >= 0 && c <= ' ')
			c = in.read();
		if (c < 0)
			return "";
		while (c > ' ') {
			b.append((char) c);
			c = in.read();
		}
		return b.toString();
	}

	public static void main(String[] args) throws Throwable {

		if (test) { // run all cases from testfile:
			BufferedReader testdataReader = new BufferedReader(new FileReader(testDataFile));
			String readLine = testdataReader.readLine();
			int casenr = 0;
			out: while (true) {
				BufferedWriter w = new BufferedWriter(new FileWriter(feedFile));
				if (!readLine.equalsIgnoreCase("input")) {
					break;
				}
				while (true) {
					readLine = testdataReader.readLine();
					if (readLine.equalsIgnoreCase("output")) {
						break;
					}
					w.write(readLine + "\n");
				}
				w.close();
				System.out.println("Answer on case " + (++casenr) + ": ");

				new MyB131().solve();
				System.out.println("Expected answer: ");

				while (true) {
					readLine = testdataReader.readLine();

					if (readLine == null) {
						break out;
					}
					if (readLine.equalsIgnoreCase("input")) {
						break;
					}
					System.out.println(readLine);
				}
				System.out.println("----------------");
			}
			testdataReader.close();
		} else { // run on server
			new MyB131().solve();
		}
		out.close();
	}

	public MyB131() throws Throwable {
		if (test) {
			in = new BufferedReader(new FileReader(new File(feedFile)));
		}
	}

	InputStreamReader inp = new InputStreamReader(System.in);
	BufferedReader in = new BufferedReader(inp);
	static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

	enum CompetitionType {
		CF, OTHER
	};
}