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.

很久很久以前。 有个可爱的小姑娘，她总是戴着红帽子。 一天，妈妈拜托小红帽说 「小红帽，外婆生病了，这里有一块点心和一瓶葡萄酒，快送到森林里的外婆家去。路上别乱 跑，小心碰到邪恶的狼」 小红帽就照吩咐出门了。 当她走进森林的时候，遇到了一只狼。狼笑眯眯的，小红帽没有防备。狼问小红帽要去哪里， 小红帽说要去外婆家。狼心里盘算着要吃掉小红帽，于是对小红帽说 「小姑娘，既然要去，不如先摘几朵盛开的鲜花带去吧」 小红帽觉得狼说的有道理，便在森林里摘起了花。 这个时候，狼抢先来到了外婆家，敲响外婆家的门。 「是谁在外面啊？」 「外婆，我是小红帽，我给你送点心和葡萄酒来了，快开门呐」 狼进了门，一口将把外婆吞进了肚子。狼戴上外婆的帽子，在床上躺了下去。等了一会儿，小 红帽来了。 小红帽进了家门，说 「哎，外婆。你的耳朵怎么这么大呀？」 「为了更清楚地听你说话呀，乖乖」 「可是外婆，你的眼睛怎么这么大呀？」 「为了更清楚地看你呀，乖乖」 「外婆，你的手怎么这么大呀？」 「可以更好地抓住你呀」 「外婆，你的嘴巴怎么大得很吓人呀？」 「可以一口把你吃掉呀！」 狼刚把话说完就从床上跳起来，向小红帽扑了过去。 然后，狼就把可怜的小红帽一口吞进了肚子。 一定要当心装好心的狼。 可喜可贺，可喜可贺。

「不要继续下去了」 「我不要！」 「我不认可上次的结束方式是幸福的结局！而且，为什么明明还没得到成果就要放弃！我绝 对，绝对不会罢手的！」

萨拉决定尽其所能帮助小红帽。 小红帽去外婆家的路可以看做是 $3$ 行 $n$ 列的方格，其中第 $2$ 行是道路，$1,3$ 行是灌木丛。 邪恶的狼可能会隐藏在灌木丛中，但灌木丛十分的茂密，所以小红帽无法看到哪些灌木里藏着狼。 萨拉给了小红帽一张魔法地图，地图可以告诉小红帽道路上每个格子的八连通分量中有几匹狼。

现在，小红帽想知道，根据这张地图，狼群的分布可能有多少种方案。

注意：邪恶的狼不会直接出现在道路之上，每个灌木丛格子中至多藏一匹狼。

输入格式​

第一行包含一个整数 $n$。

第二行共有 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示地图中 $(2,i)$ 八连通分量中狼的数量。

输入格式​

输出一个整数，表示狼群分布的方案数$(\text{mod } 10^9+7)$。

样例

输入1

2
2 2

输出1

6

输入2

10
1 1 1 1 1 2 3 5 5 4

输出2

8

数据范围与提示

对于全部数据保证 $1\le n\le 10^5,0\le a_i\le 6$。