You are given an integer array workload of length n. There are n distinct nodes, one per index, and the node at index i starts with workload[i] units. You can assume the values in workload add up to n.

Consider building a tree on all n nodes. A tree is a set of n - 1 edges that connects every node and contains no cycle. Two trees are different if some pair of nodes is joined by an edge in one of them and not in the other.

Once a tree is built, consider an operation where you pick two nodes that are exactly two edges apart in it and move one unit from the first to the second. The first node must hold at least one unit. You can perform this operation any number of times.

A tree is balanced if some sequence of operations leaves every node holding exactly one unit.

Return the number of balanced trees. Mod the result by 10 ** 9 + 7.

Examples

Example 1

Input: workload = [1,1,1]
Output: 3
Explanation: Every tree on 3 nodes is a path, and there are 3 of them, one per choice of middle node. Every node already holds one unit, so no operation is needed and all 3 trees are balanced.