2025

题目描述

给你n个数，从n个数中选出任意个数的和恰好是2025整数倍的方案数

由于方案数比较大，答案模上 $ 10^9 + 7 $

输入描述

第一行n ($ n \leq 10^4$)

第二行n个数,$ a_1,a_2,\dots,a_n $  ($ 1 \leq a_i \leq 10^9 $)

输出描述

输出方案数

提示

样例1：

• 一个数不选，和为0, 0是2025的整数倍
• 任选第一个或者第二个数都是2025的整数倍
• 两个都选和也是2025的倍数

所以方案数为4：