human
Write me a Python program to find the number of balanced arrays which are permutations of the given array given the following:
An array is called beautiful if all the elements in the array are equal.

You can transform an array using the following steps any number of times: 

  1. Choose two indices i and j (1 ≤ i,j ≤ n), and an integer x (1 ≤ x ≤ a_i). Let i be the source index and j be the sink index. 
  2. Decrease the i-th element by x, and increase the j-th element by x. The resulting values at i-th and j-th index are a_i-x and a_j+x respectively. 
  3. The cost of this operation is x ⋅ |j-i| . 
  4. Now the i-th index can no longer be the sink and the j-th index can no longer be the source. 

The total cost of a transformation is the sum of all the costs in step 3.

For example, array [0, 2, 3, 3] can be transformed into a beautiful array [2, 2, 2, 2] with total cost 1 ⋅ |1-3| + 1 ⋅ |1-4| = 5.

An array is called balanced, if it can be transformed into a beautiful array, and the cost of such transformation is uniquely defined. In other words, the minimum cost of transformation into a beautiful array equals the maximum cost.

You are given an array a_1, a_2, …, a_n of length n, consisting of non-negative integers. Your task is to find the number of balanced arrays which are permutations of the given array. Two arrays are considered different, if elements at some position differ. Since the answer can be large, output it modulo 10^9 + 7.

Input

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the size of the array. 

The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 10^9).

Output

Output a single integer — the number of balanced permutations modulo 10^9+7.

Examples

Input

3
1 2 3

Output

6

Input

4
0 4 0 4

Output

2

Input

5
0 11 12 13 14

Output

120

Note

In the first example, [1, 2, 3] is a valid permutation as we can consider the index with value 3 as the source and index with value 1 as the sink. Thus, after conversion we get a beautiful array [2, 2, 2], and the total cost would be 2. We can show that this is the only transformation of this array that leads to a beautiful array....
Using python can you solve the prior task?
assistant
#Here is Python program to find the number of balanced arrays which are permutations of the given array.

#!/usr/bin/env python
# https://github.com/cheran-senthil/PyRival
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

def main():
    fact = [1, 1] + [0] * 10 ** 5
    mod = 10 ** 9 + 7

    def mult(x, y, m):
        return ((x % m) * (y % m)) % m

    def pow(x, y, m):
        if y == 1:
            return x
        if y == 0:
            return 1
        p = pow(x, y // 2, m)
        ret = mult(p, p, m)
        if y & 1:
            return mult(ret, x, m)
        else:
            return ret

    def inv(a, p):
        return pow(a, p - 2, p)

    def div(x, y, m):
        return mult(x, inv(y, m), m)

    def ncr(n, r, m):
        if n < r:
            return 0
        if r == 0:
            return 1
        return (fact[n] * inv(fact[r], m) % m * inv(fact[n - r], m) % m) % m

    for i in range(2, 10 ** 5 + 1):
        fact[i] = mult(fact[i - 1], i, mod)

    N = int(input())
    vec = list(map(int, input().split()))
    freq = defaultdict(int)
    s = 0
    for n in vec:
        freq[n] += 1
        s += n

    if s % N:
        print(0)
    else:
        best = s // N
        src = snk = 0
        for n in vec:
            if n > best:
                src += 1
            elif n < best:
                snk += 1

        if not src or src == 1 or snk == 1:
            ans = fact[N]
            den = 1
            for _, f in freq.items():
                den = mult(den, fact[f], mod)
            ans = div(ans, den, mod)
            print(ans)
        else:
            src_perm = fact[src]
            den = 1
            for n, f in freq.items():
                if n < best:
                    den = mult(den, fact[f], mod)
            src_perm = div(src_perm, den, mod)
            snk_perm = fact[snk]
            den = 1
            for n, f in freq.items():
                if n >...