题目描述

给出一个序列 $a_1,a_2,\ldots,a_n$，要求从中选出一个子序列，使子序列中任意相邻两个数之和都是 $3$ 或 $5$ 的倍数。

能选出多少个不同的子序列？只要元素在原序列中的位置不同，就算作不同的子序列。输出答案对 $10^9+7$ 取模的结果。

输入格式

第一行，一个正整数 $n$。

第二行，$n$ 个正整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出答案对 $10^9+7$ 取模的结果。

输入输出样例

输入 #1

3
2 7 7

输出 #1

2

说明/提示

样例中，选择 $\{a_1,a_2\}$ 或 $\{a_1,a_3\}$ 都满足要求。

数据范围

$2\le n\le 3000$，$1\le a_i\le 10^9$。

3
2 7 7

2

4
331529884 996094109 600243847 660348638

7

12
648565910 253442119 709623325 64640554 655749777 454661549 433159355 778739404 293648442 103932361 621129171 532053864

174