Bobo finds a strange prime P = 10¹⁰ + 19 in ICPCCamp, and he decides to write n integers x₁, x₂, . . . , x_n
whose sum is a multiple of P, while x_i should satisfy 0 ≤ x_i < P − a_i for given a₁, a₂, . . . , a_n.
Bobo would like to know the number of different ways to write x₁, x₂, . . . , x_n modulo (10⁹ + 7).

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₁, a₂, . . . , a_n.
• 1 ≤ n ≤10⁵
• 0 ≤ ai≤ 10⁵
• The sum of n does not exceed 10⁶.

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

2
0 0
3
0 1 2

999999956
2756

2017年四川省赛