blobhyperthink

블롭은 쉬는 시간에 문제 하나를 생각해 냈다.

길이가 $N$인 수열 $A$에서 다음 조건을 만족하는 $(i, j)$ 쌍의 개수를 구하자!

• $i < j$이고 $A_i < A_j$이다.

이 문제는 블롭에게 너무 쉬웠다. 그래서 블롭은 쌍의 원소 수를 세 개로 늘렸다. 그래도 너무 쉬워서 네 개로 늘렸다. ...

그래도 너무 쉬워서 열 개로 늘렸고, 다시 열한 개로 늘렸다. 이제 이 문제는 블롭에게 너무 어려워서 풀 수 없었다!

블롭을 위해 다음 조건을 만족하는 $(i, j, k, l, m, o, p, q, r, s, t)$ 쌍의 개수를 $10^9+7$로 나눈 나머지를 구하자.

• $i < j < k < l < m < o < p < q < r < s < t$이고, $A_i < A_j < A_k < A_l < A_m < A_o < A_p < A_q < A_r < A_s < A_t$이다.

첫째 줄에 수열의 길이 $N$이 주어진다.

둘째 줄에 수열의 원소를 나타내는 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.

첫째 줄에 조건에 맞는 쌍의 개수를 $10^9+7$로 나눈 나머지를 출력한다.

• $1 \le N \le 10^5$
• $1 \le A_i \le N$ $(1 \le i \le N)$