Kyoya Ootori has a bag with n colored balls that are colored with k different colors. The colors are labeled from 1 to k. Balls of the same color are indistinguishable. He draws balls from the bag one by one until the bag is empty. He noticed that he drew the last ball of color i before drawing the last ball of color i + 1 for all i from 1 to k - 1. Now he wonders how many different ways this can happen. 

Input

The first line of input will have one integer k (1 ≤ k ≤ 1000) the number of colors.

Then, k lines will follow. The i-th line will contain ci, the number of balls of the i-th color (1 ≤ ci ≤ 1000).

The total number of balls doesn't exceed 1000.

Output

A single integer, the number of ways that Kyoya can draw the balls from the bag as described in the statement, modulo 1 000 000 007. 

Examples

Input

3
2
2
1


Output

3


Input

4
1
2
3
4


Output

1680

Note

In the first sample, we have 2 balls of color 1, 2 balls of color 2, and 1 ball of color 3. The three ways for Kyoya are: 
    
    
      
    1 2 1 2 3  
    1 1 2 2 3  
    2 1 1 2 3  
    
import java.io.*;
import java.util.*;

public class A
{
    static int n, k;
    static int[] arr;
    static char[] s;
    public static void main(String[] args) throws IOException
    {
        f = new Flash();
        out = new PrintWriter(System.out);
        
        int T = 1; //ni();
        for(int tc = 1; tc <= T; tc++){
            k = ni(); arr = arr(k); sop(fn());
        }
        
        out.flush(); out.close();
    }
    
    static long fn()
    {
        pre();
        long ans = 1;
        int total = 0;
        for(int i = 0; i < k; i++){
            ans *= ncr(total+arr[i]-1, arr[i]-1);
            ans %= mod;
            total += arr[i];
        }
        
        return ans;
    }
    
    static Flash f;
    static PrintWriter out;
    static final long mod = (long)1e9+7;
    static final long inf = Long.MAX_VALUE;
    static final int _inf = Integer.MAX_VALUE;
    static final int maxN = (int)5e5+5;
    static long[] fact, inv;
    
    static long pow(long x, long p){
        long ans = 1;
    	while(p > 0) {
    		if((p&1) == 1) ans = (ans*x) % mod;
    		x = (x*x) % mod;
    		p >>= 1;
    	}
    	
    	return ans;
    }
     
    static long mod_inv(long x){
        return pow(x, mod-2);
    }
     
    static void pre()
    {
        fact = new long[maxN+1]; fact[0] = 1;
        inv = new long[maxN+1]; inv[0] = 1;
        
        for(int i = 1; i < maxN; i++)
            fact[i] = fact[i-1] * i % mod;
            
        inv[maxN - 1] = mod_inv(fact[maxN - 1]);
        
        for (int i = maxN-2; i > 0; i--)
            inv[i] = inv[i+1] * (i+1) % mod;
    }
     
    static long ncr(int n, int r){
        if (n < 0 || r < 0 || n - r < 0) return 0;
        return fact[n] * inv[r] % mod * inv[n-r] % mod;
    }
     
    static long npr(int n, int r){
        if (n < 0 || r < 0 || n - r < 0) return 0;
        return fact[n] * inv[n-r] % mod;
    }
    
    static void sort(int[] a){
        List<Integer> A = new ArrayList<>();
        for(int i : a) A.add(i);
        Collections.sort(A);
        for(int i = 0; i < A.size(); i++) a[i] = A.get(i);
    }
    
    static long gcd(long a, long b){
        if(b == 0) return a;
        return gcd(b, a%b);
    }
    
    static void print(int[] a){
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < a.length; i++) sb.append(a[i] + " ");
        sop(sb);
    }
    
    static int swap(int itself, int dummy){return itself;}
    static void sop(Object o){out.println(o);}
    static int ni(){return f.ni();}
    static long nl(){return f.nl();}
    static double nd(){return f.nd();}
    static String next(){return f.next();}
    static String ns(){return f.ns();}
    static char[] nc(){return f.nc();}
    static int[] arr(int len){return f.arr(len);}
    
    static class Flash
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        
        String next(){
            while(!st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch(IOException e){
                    e.printStackTrace();
                }
            }
            
            return st.nextToken();
        }
        
        String ns(){
            String s = new String();
            try{
                s = br.readLine().trim();
            }catch(IOException e){
                e.printStackTrace();
            }
            
            return s;
        }
        
        int[] arr(int n){
            int[] a = new int[n];
            for(int i = 0; i < n; i++) a[i] = ni();
            return a;
        }
        
        char[] nc(){return ns().toCharArray();}
        int ni(){return Integer.parseInt(next());}
        long nl(){return Long.parseLong(next());}
        double nd(){return Double.parseDouble(next());}
    }
}