Statistics

Bear Limak was chilling in the forest when he suddenly found a computer program. The program was a correct implementation of MergeSort. Below you can find the program in pseudocode.

# mergeSort(left,right) sorts elements left, left+1, ..., right-1 of a global array T
function mergeSort(left,right):
    # if there is at most one element, we are done
    if left+1 >= right: return

    # otherwise, split the sequence into halves, sort each half separately
    mid = (left + right) div 2
    mergeSort(left,mid)
    mergeSort(mid,right)

    # then merge the two halves together
    merged = []    # an empty sequence
    p1 = left
    p2 = mid
    while (p1 < mid) or (p2 < right):
        if p1 == mid:
            merged.append( T[p2] )
            p2 += 1
        else if p2 == right:
            merged.append( T[p1] )
            p1 += 1
        else:
            if LESS( T[p1], T[p2] ):
                merged.append( T[p1] )
                p1 += 1
            else:
                merged.append( T[p2] )
                p2 += 1

    # finally, move the merged elements back into the original array
    for i from left to right-1 inclusive:
        T[i] = merged[i-left]

Limak noticed that one part of the implementation was missing: the function LESS. You can probably guess that the function is supposed to return a boolean value stating whether the first argument is less than the second argument. However, Limak is a bear and he didn't know that. Instead he implemented his own version of this function. Limak's function uses a true random number generator. Each of the two possible return values (true, false) is returned with probability 50 percent.

The random values generated in different calls to Limak's function LESS are mutually independent. Note that even if you call LESS twice with the same arguments, the two return values may differ.

After implementing LESS, Limak decided to run his brand new program. He initialized the global array T to contain N elements. Then, he filled the values 1 through N into the array: for each valid i, he set T[i] to i+1. Finally, he executed the function mergeSort(0,N).

Even with Limak's new LESS function, the program never crashes. On the other hand, it does not necessarily produce a sorted sequence when it terminates. In general, when the program terminates, the array T will contain some permutation of the numbers 1 through N.

After running the program many times, Limak has noticed that different output permutations are produced with different probabilities. Your task is to help him learn more about these probabilities.

Imagine a list of all N! permutations of numbers 1 through N. For each such permutation P we have computed the probability prob(P) that Limak's program outputs P. We will now order all those N! permutations according to that probability in descending order. (I.e., the most probable permutations are at the beginning of the list.) Ties are broken using lexicographic order. (I.e., if two permutations have exactly the same probability, the lexicographically smaller one is sooner in the list.)

You are given a int[] sortedSequence with N elements, containing a permutation of 1 through N. Let X be the 1-based index of this permutation in the list defined above. Compute and return the value (X modulo 1,000,000,007).