会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
题目要求从数组中选出若干元素组成子序列，使得子序列元素之和既是 3 的倍数又是 5 的倍数，但不能是 4 的倍数。
- “既是 3 的倍数又是 5 的倍数”等价于 该和是 15 的倍数。
- 在 15 的倍数中剔除 4 的倍数，相当于要求 和是 15 的倍数但不是 60 的倍数（因为 15 和 4 的最小公倍数是 60）。
- 在模 60 的意义下，15 的倍数有 0, 15, 30, 45；其中 0 同时也是 4 的倍数（60 的倍数），需要排除。因此满足条件的和的模 60 余数只能是 15, 30, 45。
问题转化为：求所有子序列中，元素之和模 60 等于 15、30 或 45 的方案数，对 109+7 取模。
题目内容
小蓝正在整理一些数据，她非常偏爱数字 3 和 5，却不想看到数字 4 的影子。现在她手头有一个数组，她想从中选出若干元素构成一个子序列，使得子序列中所有元素的和既是 3 的倍数，又是 5 的倍数，但不能是 4 的倍数。
请你帮她计算一共有多少种不同的子序列满足上述条件。由于答案可能非常大，请输出结果对 109+7 取模后的值。
数组的长度不超过 105，每个元素为不超过 109 的正整数。
输入描述
第一行包含一个整数 n（1≤n≤105），表示数组的长度。
