小红又战小紫
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小红上次输给了小紫，表示不服，于是又约来小紫来玩一个游戏。
这次是取石子游戏：共有n堆石子，两人轮流使用以下两种技能中的一种进行取石子：
1. 随机选择某一堆石子，取走其中的一颗石子。
2. 每一堆石子各取走一颗石子。

小红先手，谁先取完所有的石子谁获胜。两人都希望自己的获胜概率尽可能高，假设两人都绝顶聪明，请你计算小红最终获胜的概率。

输入描述:

第一行输入一个正整数n，代表石子的堆数。
第二行输入n个正整数a_i，代表每一堆石子的数量。
1\leq n \leq 1000
1\leq a_i \leq 2

输出描述:

一个整数，代表小红最终获胜的概率对10^9+7取模的值。可以证明，最终的答案一定是个有理数，你只需要输出其对10^9+7取模的结果。
分数取模的定义：假设答案是x/y，那么其对p取模的答案是找到一个整数a满足a∈[0,p-1]且a*y对p取模等于x。
示例1

输入

复制 
2
1 2

输出

复制 
500000004

说明

显然小红会使用 1 技能，因为如果使用 2 技能则必输。
小红有1/2的概率取走第一堆石子的 1 颗（此后无论小紫怎么取，小红必胜），有1/2的概率取走第二堆石子的 1 颗（此时小紫只需要直接使用 2 技能则获胜，小红失败），因此小红最终获胜的概率是 1/2。因为 500000004*2=1000000008，对10^9+7取模恰好等于 1，所以输出 500000004。