blobhyperthink

BOJ에 있는 문제를 본 블롭은 쉬는 시간에 이런 문제를 생각해 냈다.

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

$i \lt j$ 이고 $A\_i \lt A\_j$ 이다.

이 문제는 블롭에게 너무 쉬웠고, 블롭은 쌍의 원소 수를 세 개로 늘렸다. 하지만, 아직 이 문제는 블롭에게 너무 쉬웠고, 블롭은 쌍의 원소 수를 네 개로 늘렸다. ...

하지만, 아직 이 문제는 블롭에게 너무 쉬웠고, 블롭은 쌍의 원소 수를 열 개로 늘렸다. 하지만, 아직 이 문제는 블롭에게 너무 쉬웠고, 블롭은 쌍의 원소 수를 열한 개로 늘렸다. 이제 이 문제는 블롭에게 너무 어려워서 풀 수 없었다!

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

$i \lt j \lt k \lt l \lt m \lt o \lt p \lt q \lt r \lt s \lt t$ 이고, $A\_i \lt A\_j \lt A\_k \lt A\_l \lt A\_m \lt A\_o \lt A\_p \lt A\_q \lt A\_r \lt A\_s \lt A\_t$ 이다.

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

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

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