시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 512 MB111100.000%

문제

An integer sequence $a$ is rebound sequence if there are three integers $i$, $j$, $k$ ($1 \le i < j < k \le N$) satisfying $a_i > a_k > a_j$. You are given an integer sequence $s$. Your task is to count the number of rebound sequences that can be obtained by permuting the elements of $s$.

입력

The input consists of a single test case in the format below.

$N$

$s_1$ $s_2$ $\dots$ $s_N$

The first line contains a single integer $N$ ($1 \le N \le 200$). The second line contains $N$ integers $s_i$ ($1 \le s_i \le N$), which is the $i$-th element of $s$.

출력

Output the number of rebound sequences that can be obtained by permuting the elements of $s$ modulo $10^9 + 7$.

예제 입력 1

4
1 2 3 4

예제 출력 1

10

예제 입력 2

12
1 2 3 4 5 6 7 8 9 10 11 12

예제 출력 2

478793588

예제 입력 3

5
3 1 4 1 5

예제 출력 3

32

예제 입력 4

20
1 1 1 2 3 4 4 7 7 8 11 12 13 14 15 16 17 17 19 20

예제 출력 4

959127228