1443 - 木棍拼接
描述

nn 根木棒,现在从中选 44 根,想要组成一个正三角形,问有几种选法?

答案对 109+710^9+7 取模。


输入

第一行一个整数 nn

第二行往下 nn 行,每行 11 个整数,第 ii 个整数 aia_i 代表第 ii 根木棒的长度。


输出

一行一个整数代表答案。

样例

输入
复制

4 
1
1
2
2

输出
复制

1
提示

- 对于 30%30\% 的数据,保证 n5×103n \le 5 \times 10^3

- 对于 100%100\% 的数据,保证 1n1051 \leq n \le 10^51ai5×1031 \le a_i \le 5 \times 10^3


题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 21
通过次数 1