题目描述

有 $n$ 面旗帜，第 $i$ 面旗帜的颜色是 $col_i$。现在千夜老师想要从中选取两面颜色一样的旗帜，请问千夜老师有几种不同的方案？由于方案数可能很多，请输出方案数对 $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

2

5
1 2 1 2 1

4

5
1 1 1 1 1 

10

数据范围

对于 $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$。