Particular Particles

Lauren is conducting an experiment to test an apparatus. She expects the black box to perform in the following way. Given \(n\) particles of \(k\) types, the box will act on the particles at each step such that \(k-1\) particles are selected, all of differing types. These particles are then transformed into the remaining type of particle. Lauren wants to know in how many combinations of particles are possible for her to observe. As this answer can be very large it should be \(mod\) \(1000000007\)

Input Specification

The first line contains one integer \(k\) The second line contains \(k\) space seperated integers \(a_i\) denoting the count of \(i\)th particle type, hence \(\sum_{i=1}^{k}{a_i} = n\)

Output Specification

Output one integer \(c\) the number of combinations lauren may observe \(mod\) \(1000000007\)

Bounds

\(2 \leq k \leq 10^5\)
\(1 \leq n \leq 10^6\)

Sample Input

3
0 1 2

Sample Output

3

Explanation

at the first step the particles of type \(a_2\) and \(a_3\) are selected hence the next combination would be [2, 0, 1]
at the second step the particles of type \(a_1\) and \(a_3\) are selected hence the next combination would be [1, 2, 0]
there are no cobinations left after this point as the next step would lead to our original state
hence the answer is 3 as we count the original state as a combination