Sum of Inversion Counts over Permuted Subsequences

Given a permutation \(a_{[1,n]}\) of \(1\sim n\), for each \(i\) (\(1 \le i \le n\)) consider the following operation on the prefix \(a_{[1,i]}\):

• Select an arbitrary subsequence (possibly empty) from the first \(i\) elements.
• Rearrange the numbers in the chosen subsequence in an arbitrary order.

Although the operation is not actually applied to the permutation, each operation sequence produces a hypothetical resulting permutation. Two operation sequences are considered different if either the chosen subsequence or its rearrangement differ.

Your task is to calculate the sum of the inversion counts of the resulting permutations produced by all different operation sequences, over all \(i\) from \(1\) to \(n\). Since the answer can be large, output it modulo \(20051131\). Note that an inversion in a permutation \(b_1,b_2,\dots,b_n\) is a pair \((p,q)\) with \(1 \le p b_q\).

The following is an illustration:

For a prefix of length \(i\), if no element is selected the prefix remains unchanged; if some indices are selected then the elements at those positions can be arbitrarily rearranged, and are then placed back into the original positions. The suffix \(a_{[i+1,n]}\) remains unchanged throughout. The inversion count of the full permutation is computed in the usual manner.

inputFormat

The first line contains an integer \(n\) (we guarantee \(1 \le n \le 8\)). The second line contains \(n\) distinct integers representing the permutation \(a_{[1,n]}\) (a permutation of \(1,2,\dots,n\)).

outputFormat

Output a single integer, which is the sum of inversion counts (over all chosen operation sequences for all prefixes) modulo \(20051131\).

sample

1
1

0