pjy 已经被 ACM 打趴在地上，再也不想看到 2,3,5 这三个数字了。

捣蛋鬼 cjh 故意在纸上写长度为 n 的序列 A，它们只包含 2,3,5。同时,cjh 每写完一个数，lre 记录该数字出现的次数，得到序列 B。例如:

• 如果 cjh 写 A=[2, 2, 3, 2, 5, 5, 5]，那么 lre 会依次写 B=[ 1, 2, 1, 3, 1, 2, 3]
• 如果 cjh 写 A=[3, 3, 3, 3, 3]，那么 lre 会依次写 B=[ 1, 2, 3, 4, 5]

做完这个过程之后，cjh 把他写的序列扔掉，只保留 lre 写的序列，然后跑去问 pjy，”请找到一个只包含 2,3,5 的序列，且按照 lre 记录的规则，能得到 B 序列”。

pjy 真的不想再看到 2,3,5 这三个数字了，所以现在请你帮忙。

第一行表示一个数 n(1 ≤ n ≤ 1000000)

第二行 n 个数，用空格隔开，表示 lre 写的序列 B。

仅一行，表示答案，即 A 序列有多少种可能（由于答案有可能很大,你只需要输出答案除以 1000000007 取余数的结果）