你的朋友 Tóti 是一位有抱负的音乐家。他创作了 $n$ 首歌曲，每首歌的“热度评分”（hype rating）为 1、2 或 3。热度评分越高，意味着歌曲的能量越高。Tóti 正在筹划他的第一场现场演出，需要你的帮助。他想知道他能组成多少种“歌单”（setlist）。一个歌单至少包含三首歌，第一首歌的热度评分必须为 1，最后一首歌的热度评分必须为 3，且所有中间的歌曲热度评分必须为 2。此外，Tóti 希望按照他创作歌曲的原始顺序来演奏它们。

给定 Tóti 创作的每首歌的热度评分（按创作顺序），他能组成多少种歌单？

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示 Tóti 创作的歌曲数量。第二行包含 $n$ 个整数，每个整数都在 $\{1, 2, 3\}$ 中，按创作顺序给出了这 $n$ 首歌的热度评分。

输出格式

输出 Tóti 能组成的歌单数量。由于这个数字可能很大，请输出其对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

9
1 1 1 2 2 2 3 3 3

样例输出 1

63

样例输入 2

8
1 2 1 2 3 1 2 3

样例输出 2

15