有 nnn 根木棒,现在从中选 444 根,想要组成一个正三角形,问有几种选法?
答案对 109+710^9+7109+7 取模。
第一行一个整数 nnn。
第二行往下 nnn 行,每行 111 个整数,第 iii 个整数 aia_iai 代表第 iii 根木棒的长度。
一行一个整数代表答案。
4 1 1 2 2
1
- 对于 30%30\%30% 的数据,保证 n≤5×103n \le 5 \times 10^3n≤5×103。
- 对于 100%100\%100% 的数据,保证 1≤n≤1051 \leq n \le 10^51≤n≤105,1≤ai≤5×1031 \le a_i \le 5 \times 10^31≤ai≤5×103。