#HT1064. 同色旗帜对计数

同色旗帜对计数

题目描述

nn 面旗帜,第 ii 面旗帜的颜色是 colicol_i。现在千夜老师想要从中选取两面颜色一样的旗帜,请问千夜老师有几种不同的方案?由于方案数可能很多,请输出方案数对 1,000,000,0071,000,000,007 取余后的结果。

假设两个方案分别选取 cola,colbcol_a,col_bcolx,colycol_x,col_y,那么只要 “a=xa=x并且b=yb=y” 或 “a=ya=y 并且 b=xb=x”,我们就说这两个方案是同一种方案。反之则为不同方案。

输入格式

输入第一行为一个整数 nn,即旗帜数量。

接下来一行为空格隔开的 nn 个整数,第 ii 个整数为 colicol_i,即旗帜颜色。

输出格式

输出一行,为方案数对 1,000,000,0071,000,000,007 取余后的结果。

样例

5
1 4 1 5 5
2
5
1 2 1 2 1
4
5
1 1 1 1 1 
10

数据范围

对于 60%60\% 的数据:1n10001\le n\le 10001coli10001\le col_i\le 1000

对于 100%100\% 的数据:1n1061\le n\le 10^61coli1061\le col_i\le 10^6