You are given a permutation *p*. Calculate the total number of inversions in all permutations that lexicographically do not exceed the given one.

As this number can be very large, print it modulo 1000000007 (10<sup class="upper-index">9</sup> + 7).
The first line contains a single integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">6</sup>) — the length of the permutation. The second line contains *n* distinct integers *p*<sub class="lower-index">1</sub>, *p*<sub class="lower-index">2</sub>, ..., *p*<sub class="lower-index">*n*</sub> (1 ≤ *p*<sub class="lower-index">*i*</sub> ≤ *n*).


n = int(input())
numbers = list()
for i in range(n):
    numbers.append(int(input()))

count = 0

def merge(numbers1, numbers2):
    j = 0
    k = 0
    global count
    merged = list()
    for i in range(len(numbers1)+len(numbers2)):

        if j >= len(numbers1) and k < len(numbers2):
            return merged + numbers2[k:]
        
        if k >= len(numbers2) and j < len(numbers1):
            return merged + numbers1[j:]
    

        if numbers1[j] <= numbers2[k]:
            merged.append(numbers1[j])
            j+=1
        else:
            count= (count % 1000000007)+1
            merged.append(numbers2[k])
            k+=1

    return merged

def mergeSort(numbers):
    if len(numbers) < 2:
        return numbers

    middle = len(numbers)//2

    l1 = mergeSort(numbers[:middle])
    l2 = mergeSort(numbers[middle:])
    return merge(l1, l2)




mergeSort(numbers)
print(count)
