/**
* Method: Recurrence relation. Coefficients of the recurrence are defined
* manually by looking at the state diagram.
*
* Author: Catalin Francu
**/
#include <stdio.h>
#define MAX_VALUE 1000000
#define MOD 1000000007
typedef unsigned long long u64;
typedef struct {
u64 a, b, c, d, e, f, g, h, i;
} row;
row p, q;
/* frequencies of array elements */
int freq[MAX_VALUE + 1];
/* precomputing this can cut the running time by some 20% */
int choose(int n, int k) {
switch (k) {
case 0: return 1;
case 1: return n;
case 2: return (u64)n * (n - 1) / 2 % MOD;
case 3: return (u64)n * (n - 1) * (n - 2) / 6 % MOD;
default: return 0; /* should be unreachable */
}
}
/* combinations with repetition: how many ways are there of placing n */
/* identical balls into k non-identical urns? */
int chooseRep(int n, int k) {
return choose(n + k - 1, k - 1);
}
u64 helper(int value, int newBits, int totalBits, int freq) {
return (freq >= newBits)
? (u64)value * chooseRep(freq - newBits, totalBits)
: 0;
}
int main() {
/* read input data; we only care about element frequencies */
int n, x;
scanf("%d", &n);
while (n--) {
scanf("%d", &x);
freq[x]++;
}
p.a = 1;
for (int v = 1; v <= MAX_VALUE; v++) {
if (freq[v]) {
q.a = 0;
q.b = (helper(p.a, 1, 1, freq[v]) +
helper(p.b, 0, 1, freq[v])) % MOD;
q.c = (helper(p.b, 1, 2, freq[v]) +
helper(p.c, 0, 2, freq[v])) % MOD;
q.d = (helper(p.a, 2, 2, freq[v]) +
helper(p.b * 2, 1, 2, freq[v]) +
helper(p.d, 0, 2, freq[v])) % MOD;
q.e = (helper(p.b, 2, 3, freq[v]) +
helper(p.c, 1, 3, freq[v]) +
helper(p.d, 1, 3, freq[v]) +
helper(p.e, 0, 3, freq[v])) % MOD;
q.f = (helper(p.d, 1, 1, freq[v])) % MOD;
q.g = (helper(p.d, 2, 2, freq[v]) +
helper(p.e, 1, 2, freq[v]) +
helper(p.f, 1, 1, freq[v]) +
helper(p.g, 0, 1, freq[v])) % MOD;
q.h = (helper(p.d, 2, 4, freq[v]) +
helper(p.e * 2, 1, 4, freq[v]) +
helper(p.h, 0, 4, freq[v])) % MOD;
q.i = (helper(p.d, 3, 3, freq[v]) +
helper(p.e * 2, 2, 3, freq[v]) +
helper(p.f, 2, 2, freq[v]) +
helper(p.g * 2, 1, 2, freq[v]) +
helper(p.h, 1, 3, freq[v]) +
helper(p.i, 0, 2, freq[v])) % MOD;
p = q;
}
}
printf("%llu\n", p.i);
}
