Road Network 2

Time limit5sMemory limit128 MB

Summary

Count the labeled trees that realize a prescribed degree sequence, or report that none exist, with n up to two million.

Level: Medium6 of 10
Topics: Tree, Combinatorics, Math
Solved: No attempts yet

Problem

Byteland has $n$ cities, numbered $1$ through $n$ . Every road is bidirectional and connects two different cities. Between any two different cities there is exactly one path of roads that visits no city more than once. In other words, the road network is a tree with $n$ vertices and $n-1$ edges.

We want to build a road network in which exactly $d_i$ roads meet at city $i$ (that is, city $i$ has degree $d_i$ ). Many different networks may satisfy these conditions. Determine how many different road networks satisfy them. Cities carry distinct labels, so two networks are considered different whenever their sets of roads differ.

Input

The first line contains an integer $n$ ( $2 \le n \le 2000000$ ). The second line contains $n$ integers $d_1, d_2, \ldots, d_n$ ( $1 \le d_i \le n-1$ ) separated by spaces, where $d_i$ is the degree of city $i$ .

Output

If no road network satisfies the conditions, print BRAK (Polish for 'none') on the only line. Otherwise, print the number of different road networks that satisfy the conditions, modulo 1,000,000,007.

Hint

Examples4

Example 1
Input
```
6
1 1 3 3 1 1
```
Expected output
```
6
```
Example 2
Input
```
2
1 1
```
Expected output
```
1
```
Example 3
Input
```
3
1 1 1
```
Expected output
```
BRAK
```
Example 4
Input
```
3
2 1 1
```
Expected output
```
1
```