#P1809. 2024.4.8-ali-第三题-塔子哥追剧

2024.4.8-ali-第三题-塔子哥追剧

题目描述

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

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

输入描述

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

第二行输入nn个整数a(1≤ai≤109)a(1\le a_i\le 10^9)表示数组

输出描述

输出一个整数表示答案

样例

输入

3
13 30 17

输出

2

说明

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

知识点:*****

查看知识点以及同类型题目

Statistics