Bobo finds a strange prime $P = 10^{10} + 19$ in ICPCCamp, and he decides to write $n$ integers $x_1, x_2, \dots, x_n$ whose sum is a multiple of $P$, while $x_i$ should satisfy $0 \leq x_i < P - a_i$ for given $a_1, a_2, \dots, a_n$.

Bobo would like to know the number of different ways to write $x_1, x_2, \dots, x_n$ modulo $(10^9+7)$.

Input

The input contains zero or more test cases and is terminated by end-of-file. For each test case:

The first line contains an integer $n$. The second line contains $n$ integers $a_1, a_2, \dots, a_n$.

• $1 \leq n \leq 10^5$
• $0 \leq a_i \leq 10^5$
• The sum of $n$ does not exceed $10^6$.

Output

For each case, output an integer which denotes the number of different ways.

Sample Input

2
0 0
3
0 1 2

Sample Output

999999956
2756