QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB
[+1]

# 3724. Strange Prime

Statistics

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 0xi<Pai 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.

  • 1n105
  • 0ai105
  • 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