You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目内容

塔子哥参加了2023的春招全过程。在这些做过的题目里，有一类题目出现的非常多，那就是数数题 。现在塔子哥闭上眼睛都是这些题。能解决这个问题的唯一办法就是自己出一道数数题！这个数数题描述为：

给定一个序列$a$ , 这个序列的元素有两种状态 ， 对于第$i$个元素$a_i$ 和其状态$s_i$:

1.如果$a_1,a_2,...a_{i-1}$ 中不存在下标$j$ 使得$a_j = a_i$ , 那么:

1.1 如果$a_1,a_2,...a_{i-1}$ 中存在下标$j$ 使得$|a_j - a_i| = 1$ , 那么其状态$s_i$为$1$

1.2 否则，其状态$s_i$为$0$

2.否则 $s_i = s_j$

对于一个序列$a$ , 我们令度$d(a) = \sum_{i=1}^{|a|} s_i$ 。 塔子哥想问，给定一个多重集$S$，其所有可能排列的度之和是多少？即求解

答案可能很大，请对$1e9+7$ 取模!

输入描述

第一行输入一个整数$n(1 \leq n \leq 1e5)$, 代表多重集大小

第二行输入$n$个整数$s_i (1 \leq a_i \leq 1e15)$, 代表集合的元素(可能存在重复)

输出描述

输出一行代表集合的所有排列的度之和。

数据范围说明

样例1

输入

3
3 2 1

输出

10

样例解释

$a_1=[3, 2, 1] , s_1 = [0, 1, 1] , d(a_1) = 2$

$a_2=[2, 1, 3] , s_2 = [0, 1, 1] , d(a_2) = 2$

$a_3=[1, 3, 2] , s_3 = [0, 0, 1] , d(a_3) = 1$

$a_4=[2, 3, 1] , s_4 = [0, 1, 1] , d(a_4) = 2$

$a_5=[3, 1, 2] , s_5 = [0, 0, 1] , d(a_5) = 1$

$a_6=[1, 2, 3] , s_6 = [0, 1, 1] , d(a_6) = 2$

$答案为 2 + 2 + 1 + 2 + 1 + 2 = 10$

样例2

输入

3
1 1 2

输出

4

样例解释

$a_1=[1, 1, 2] , s_1 = [0, 0, 1] , d(a_1) = 1$

$a_2=[2, 1, 1] , s_2 = [0, 1, 1] , d(a_2) = 2$

$a_3=[1, 2, 1] , s_3 = [0, 1, 0] , d(a_3) = 1$

$答案为 1 + 2 + 1 = 4$