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.
// Change Of Plans BABY.... Change Of Plans //
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class numbers {

    static void MainSolution() {
        n = ni();
        int ar[] = new int[10];
        for (int i = 0; i < 10; i++) ar[i] = ni();
        long fac[] = new long[101];
        long inv[] = new long[101];
        fac[0] = 1;
        fac[1] = 1;
        inv[0] = 1;
        for (int i = 1; i < 101; i++) {
            fac[i] = fac[i - 1] * i;
            fac[i] %= mod9;
            inv[i] = inverse(fac[i]);
        }
        long dp[][] = new long[10][n + 1];
        dp[0][0] = 1;
        for (int i = 1; i < 10; i++) {
            for (int j = 0; j <= n; j++) {
                for (int k = ar[i]; j + k <= n; k++) {
                    dp[i][j + k] += dp[i - 1][j] * inv[k];
                    dp[i][j + k] %= mod9;
                }
            }
        }

        for (int i = 0; i <= n; i++) {
            dp[9][i] *= fac[i];
            dp[9][i] %= mod9;
        }

        long ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = ar[0]; i + j <= n; j++) {
                ans += dp[9][i] * fac[i + j - 1] % mod9 * inv[i - 1] % mod9 * inv[j] % mod9;
            }
        }
        pl(ans % mod9);
    }

    static long inverse(long x) {

        long res = 1;
        for (int i = mod9 - 2; i > 0; i = i >>> 1) {
            if ((i & 1) == 1) res = res * x % mod9;
            x = x * x % mod9;
        }
        return res;
    }

    /*----------------------------------------------------------------------------------------------------------------*/
    //THE DON'T CARE ZONE BEGINS HERE...\\
    static int mod9 = 1_000_000_007;
    static int n, m, l, k, t;
    static AwesomeInput input = new AwesomeInput(System.in);
    static PrintWriter pw = new PrintWriter(System.out, true);

    // The Awesome Input Code is a fast IO method //
    static class AwesomeInput {
        private InputStream letsDoIT;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        private AwesomeInput(InputStream incoming) {
            this.letsDoIT = incoming;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = letsDoIT.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        private long ForLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
            return res * sgn;
        }

        private String ForString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            }
            while (!isSpaceChar(c));

            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            boolean isSpaceChar(int ch);
        }
    }

    // functions to take input//
    static int ni() {
        return (int) input.ForLong();
    }

    static String ns() {
        return input.ForString();
    }

    static long nl() {
        return input.ForLong();
    }

    static double nd() throws IOException {
        return Double.parseDouble(new BufferedReader(new InputStreamReader(System.in)).readLine());
    }

    //functions to give output
    static void pl() {
        pw.println();
    }

    static void p(Object o) {
        pw.print(o + " ");
    }

    static void pws(Object o) {
        pw.print(o + "");
    }

    static void pl(Object o) {
        pw.println(o);
    }

    // Fast Sort is Radix Sort
    public static int[] fastSort(int[] f) {
        int n = f.length;
        int[] to = new int[n];
        {
            int[] b = new int[65537];
            for (int i = 0; i < n; i++) b[1 + (f[i] & 0xffff)]++;
            for (int i = 1; i <= 65536; i++) b[i] += b[i - 1];
            for (int i = 0; i < n; i++) to[b[f[i] & 0xffff]++] = f[i];
            int[] d = f;
            f = to;
            to = d;
        }
        {
            int[] b = new int[65537];
            for (int i = 0; i < n; i++) b[1 + (f[i] >>> 16)]++;
            for (int i = 1; i <= 65536; i++) b[i] += b[i - 1];
            for (int i = 0; i < n; i++) to[b[f[i] >>> 16]++] = f[i];
            int[] d = f;
            f = to;
            to = d;
        }
        return f;
    }

    public static void main(String[] args) {      //threading has been used to increase the stack size.

        new Thread(null, null, "Vengeance", 1 << 25)  //the last parameter is stack size desired.
        {
            public void run() {
                try {
                    double s = System.currentTimeMillis();
                    MainSolution();
                    //pl(("\nExecution Time : " + ((double) System.currentTimeMillis() - s) / 1000) + " s");
                    pw.flush();
                    pw.close();
                } catch (Exception e) {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }.start();
    }
}