递推

P1713升级版。

题目从连续子序列变成了子序列，也就是说我们需要求出所有子序列的和$mod 15$及$mod 60$的个数。

我们假设枚举到第$i$个数时，我们已经知道前$i-1$个数的子序列的所有和取模的情况，那么该如何计算加入第$i$个数的情况呢？

定义$f15[i][j]$表示前$i$个数的所有子序列和中$mod15=j$的个数。

题目描述

小红非常喜欢一部 2023 年上线的作品，但是这部作品到 2025年才能有第二季，小红觉得这个 2024 年不需要了，想直接结束2024年，因此她现在，常喜欢3和5但不喜欢4。 现在小红有一个数组，她想知道这个数组中有多少个子序列的和是3和5的倍数，但不是4的倍数。

由于这个答案可能很大，因此你需要输一答案对$10^9+7$取模后的结果。

输入描述

第一行输入一个整数$n(1\le n \le 10^5)$表示数组长度。

第二行输入$n$个整数$a(1\le a_i\le 10^9)$表示数组

输出描述

输出一个整数表示答案

样例

输入

3
13 30 17

输出

2

说明

有两个子序列满足要求:[13,17],[30]。