P2429 - 同色旗帜对计数

内存限制：256 MB 时间限制：1.000 S

评测方式：文本比较命题人：

提交：6 解决：4

提交提交记录统计流程图露一手!

有 $n$ 面旗帜，第 $i$ 面旗帜的颜色是 $col_i$ 。现在 33DAI 想要从中选取两面颜色一样的旗帜，请问 33DAI 有几种不同的方案？由于方案数可能很多，请输出方案数对 $1,000,000,007$ 取余后的结果。

假设两个方案分别选取 $col_a,col_b$ 与 $col_x,col_y$ ，那么只要 “ $a=x$ 并且 $b=y$ ” 或 “ $a=y$ 并且 $b=x$ ”，我们就说这两个方案是同一种方案。反之则为不同方案。

输入第一行为一个整数 $n$ ，即旗帜数量。

接下来一行为空格隔开的 $n$ 个整数，第 $i$ 个整数为 $col_i$ ，即旗帜颜色。

输出一行，为方案数对

1,000,000,007

取余后的结果。

5
1 4 1 5 5

样例

5
1 4 1 5 5

5
1 2 1 2 1

5
1 1 1 1 1

对于 $60\%$ 的数据： $1\le n\le 1000$ ， $1\le col_i\le 1000$ 。

对于 $100\%$ 的数据： $1\le n\le 10^6$ ， $1\le col_i\le 10^6$ 。

33QJ

提交提交记录统计露一手!