Cerința

Un război se apropie, va trebui să ajuți combatanții să afle șansele lor de victorie.

Se dă un vector cu n numere naturale, unde v[i] reprezintă numărul de valori egale cu i. Un scenariu în care omenirea câștigă e un scenariu în care suma numerelor dintr-o submulțime este multiplu de n.

De exemplu, dacă vectorul din enunț este 1 2 3, valorile pe care le avem de fapt sunt 1 2 2 3 3 3, valori pe care le putem nota ca facând parte dintr-un nou vector, vectorul a, iar numărul de valori pe care îl avem este egal cu x = v[1]+v[2]+...+v[n].

Astfel, trebuie să aflați câte din cele \({2}^{x}\) submulțimi ale vectorului a au suma multiplu de n, modulo \({10}^{9} + 7\)

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, unde v[i] reprezintă numărul de valori egale cu i.

Date de ieșire

Programul va afișa pe ecran răspunsul cerut.

Restricții și precizări

• 1 ≤ n ≤ 100
• cele n numere citite vor fi mai mici decât 200000
• Pentru 20 de puncte, suma numerelor din vector nu va depăși 20.
• Pentru 60 de puncte, suma numerelor din vector nu va depăși 100000.

Exemplu:

Intrare

3
1 1 1

Ieșire

4

Exemplu 2

Intrare

5
69 420 1017 128 953

Ieșire

985611225