很久很久以前，有个地方有一位美丽的王后。 在一个积雪的冬日里，正在做针线活儿的王后一不留神被针刺进了手指。她看到着点缀在白雪 上的鲜红血滴说 「但愿我能有一个女儿，她的皮肤长得就像这洁白的雪和鲜红的血一样白里透红，头发长得就 像这窗子的乌木一般又黑又亮！」 没多久她就生下了个想象中那样的美丽女儿。 公主茁长成长，容貌也越来越美丽动人。王后对自己的美貌非常自豪。她有一面魔镜，每天都 会走到镜子跟前提问。 「魔镜啊、魔镜。谁是这个世界上最美丽的人？」 「是您，王后。这个世界上最美丽的人是王后您」 魔镜本来应该这样回答。但在那一天，魔镜却回答说 「是白雪公主」 王后听了非常憎恨公主，开始策划杀死公主。 她叫来一个猎人，对他下令把白雪公主带到森林里去，到时候把公主的肺和肝带回来。但猎人 也不禁起了恻隐之心，便放走了公主。拿猪仔的肺和肝交给了王后。 王后用盐腌了肺和肝，吃了下去。 白雪公主逃啊逃啊，终于来到七个小矮人住的房子里。 小矮人们做完工作回到家里大吃一惊。但是，他们小矮人们十分同情她，以做家务作为条件， 答应她在家里想住多久住多久。 就这样，白雪公主和七个小矮人度过了一段平静的日子。 但好景不长，王后用魔镜知道了白雪公主还活着。 王后扮成一个卖杂货的老太婆，找到了白雪公主。第一次，她带着漂亮的束腰绳过去，勒紧公 主的腰杀掉了公主。第二次她带着读梳子过去，插在公主头发上杀掉了公主。但公主这两次都被小 孩子救了下来，死而复生。 然后第三次，王后把毒苹果喂给了公主。

『【没能获得幸福的故事】到底能否改变？』 「你真的有信心让这个故事变得幸福吗？」 「有，没信心的话我就不会打开它了。只要好好努力肯定会顺利的！」

萨拉回忆自己翻开的故事里的内容，她发现，皇后的毒苹果会盛放在 $n$ 个盘子中。 盘子的编号依次从 $1$ 到 $n$，第 $i$ 个盘子里会有 $a_i$ 个苹果。 现在，萨拉可以施展魔法，选择一个盘子使其中的苹果数量减一。 受限于萨拉的魔法水平，每次选出的盘子是随机的，如果选出了一个空盘子，那么这就是一次无效的魔法。 现在萨拉想知道，要使皇后所有的毒苹果都消失，她需要施展魔法次数的期望为多少。

输入格式​

第一行包含一个整数 $n$，表示皇后拥有盘子的个数。

第二行包含 $n$ 个整数，其中第 $i$ 个整数 $a_i$ 表示 $i$ 号盘子中苹果的个数。

输出格式

输出一个整数，为萨拉需要施展魔法次数的期望在$\text{mod } 10^9+7$ 的意义下。

样例

输入1

2
1 2

输出1

500000008

输入2

3
1 1 1

输出2

500000009

数据范围与提示

对于全部的测试点，保证 $1 \le n \le 300$，$1\le a_i\le 3$。