You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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

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

萨拉回忆自己翻开的故事里的内容，她发现，皇后的毒苹果会盛放在 $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$。