Bobo finds a strange prime P=1010+19 in ICPCCamp, and he decides to write n integers x1,x2,…,xn whose sum is a multiple of P, while xi should satisfy 0≤xi<P−ai for given a1,a2,…,an.
Bobo would like to know the number of different ways to write x1,x2,…,xn modulo (109+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 a1,a2,…,an.
- 1≤n≤105
- 0≤ai≤105
- The sum of n does not exceed 106.
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