도로망 2

바이트제(Byteland)에는 $1$번부터 $n$번까지 번호가 매겨진 $n$개의 도시가 있다. 모든 도로는 양방향이며 서로 다른 두 도시를 잇는다. 서로 다른 임의의 두 도시 사이에는 같은 도시를 두 번 이상 지나지 않는 도로들의 경로가 정확히 하나 존재한다. 즉, 도로망은 $n$개의 정점과 $n-1$개의 간선으로 이루어진 트리이다.

각 도시 $i$에 연결된 도로의 수(차수)가 정확히 $d_i$가 되도록 도로망을 만들려고 한다. 이 조건을 만족하는 도로망은 매우 많을 수 있다. 조건을 만족하는 서로 다른 도로망이 모두 몇 가지인지 구하여라. 도시마다 서로 다른 번호가 붙어 있으므로, 간선의 집합이 다르면 서로 다른 도로망으로 센다.

첫째 줄에 정수 $n$ ($2 \le n \le 2000000$)이 주어진다. 둘째 줄에 $n$개의 정수 $d_1, d_2, \ldots, d_n$ ($1 \le d_i \le n-1$)이 공백으로 구분되어 주어진다. $d_i$는 $i$번 도시의 차수이다.

조건을 만족하는 도로망이 하나도 존재하지 않으면 첫째 줄에 BRAK(폴란드어로 '없음'을 뜻한다)을 출력한다. 그렇지 않으면 조건을 만족하는 서로 다른 도로망의 수를 1,000,000,007로 나눈 나머지를 출력한다.