Background

Special for beginners, ^_^

Description

你朋友正在筹办CATV演唱会，喜迎春节，演唱会有n首已经排序的歌曲，可以选择其中若干首演唱，不能交换演唱顺序。每首歌曲只适合某一种声音类型的演唱家，分别是1低音、2中音、3高音。演唱会必须选择至少其中的三首歌曲，并且满足第一首必须是低音，最后一首必须是高音，中间的必须全部是中音。因为只有这样，才能象征日子芝麻开花节节高。现在给出每首歌曲的适合类型，问有多少种演唱列表方案？

Format

Input

第一行一个整数n（<=1e6），表示列表中的歌曲总数。 第二行按照顺序给出每首歌曲的类型（1、2或者3）。

Output

输出演唱列表的方案数(mod 1e9+7)。

Samples

9
1 1 1 2 2 2 3 3 3

63

Limitation

1s, 1024KiB for each test case.