Lukas is a little beaver who loves to play with graphs. His favorite kind of graphs to play with are trees. A tree is a connected graph with no cycles.
Recently, he defined a new structure in a tree and called it a stickman. A stickman is a set of 7 different vertices and 6 different edges. Vertices should be connected by edges as in the image below.
You can see here two legs, two arms and a head. Formally, one vertex must be connected to four other vertices and one of these four must be connected to two more vertices.
Lukas had a tree of N vertices (numbered 1 through N) and he used to count distinct stickmen in that tree. A stickman is defined by a set of vertices and edges and their order doesn't matter. So, two stickmen are distinct only if some vertex or some edge belongs to exactly one of the two stickmen.
However, one day a mischievous bear stole Lukas' tree. Now Lukas doesn't remember what his tree looked like. All he remembers is the degree of every vertex of the tree. He is sure that the degree of the vertex i was equal to Di.
He has no other choice than to assume that his tree was a random tree satisfying the conditions he remembers. More formally, let's consider the set S of all distinct trees of N vertices (numbered 1 through N) satisfying those conditions. Two trees are distinct only if there are two vertices connected by an edge in exactly one of the two trees. Limak assumes now that each tree in S has equal probability to be his beloved tree.
Note: It is guaranteed that there is at least one tree with the given degrees. So, the described set S isn't empty.
After the loss Lukas is too sad to do anything so he asks you to find the expected number of stickmen in his tree. Find the answer and print it modulo 109+7. Read the "Output format" section for more details.
Input format
The first line contains a single integer N, denoting the number of vertices in the tree.
The next line contains N integers D1, D2, ..., DN.
Output format
If the answer is equal to 0, print 0 in a single line.
Otherwise, it can be proved that for given constraints the answer can be uniquely written as a fraction P/Q satisfying conditions:
1) P and Q are positive integers
2) P and Q are relatively prime (so P/Q is an irreducible fraction)
3) Q is not divisible by 109+7
Your task is to find the value of P * Q-1 modulo 109+7.
Print it in a single line.
Constraints
2 ≤ N ≤ 105
1 ≤ Di ≤ N-1
It is guaranteed that there is at least one tree with the given degrees.
There are 3 groups of trees satisfying properties Lukas remembers.
1)
Here X represents any of the nodes with degree 1. There are 90 such trees and each of them has 2 stickmen.
2)
There are 60 such trees and each of these has 1 stickman.
3)
There are 60 such trees and each of these has 1 stickman.
The expected number of stickmen is (90*2 + 60*1 + 60*1)/(90 + 60 + 60) = 300/210 = 10/7.
7-1 mod (109+7) = 142857144.
Therefore, we print 10*142857144 mod (109+7) = 428571433
NOTE: According to the provided definition of distinct trees, the following two trees are distinct - because only one of them contains an edge 1-3.
