先思考这样一个问题，若存在一个逆序对，那么这个逆序对会被多少个子序列包含呢？数组的长度为n，除去逆序对所包含的两个元素外，其余的元素都有存在或者不存在两种选择，由此构成的子序列数量应为2^(n-2)个。

显而易见，最终答案就是逆序对数量乘以 2^(n-2)。

而求逆序对数量有多种实现方法，常见的有并归排序和树状数组。这里我使用的是树状数组。

原数组a，其中元素的最大值为maxa。那么创建一个树状数组c，长度为maxa+1。当我们要统计数组值中小于等于x的元素个数的时候，可以将其分解为若干个区间。以数字7为例，统计数组中小于等于7的元素的个数。那么ans = c[7] + c[6] + c[4]。其中c[4]值为区间[1, 4]的个数，c[6]值为区间[5, 6]的个数，c[7]为区间[7, 7]的个数。

一般的，c[x]值为区间[x - lowbit(k) + 1, x]的个数。我们在写函数query时只要做一个递归即可。

接下来是update函数，也就是向数组a中添加元素x。那么c[x]的值+1，同时x的所有祖先，在数组c中的元素值+1。比如我们要向数组添加元素1。那么c[1]++，c[2]++，c[4]++，c[8]++，以此类推。

将树状数组的函数写好后，接下来将数组a从后往前遍历。每当取得一个元素a[i]，查询比a[i]小的数有几个，每有一个都构成一个逆序对。查询完毕后将a[i]加入到数组。

下面是代码。

#include <iostream>
#include <vector>
using namespace std;

const int mod = 1e9 + 7;
vector<int> c;

int lowbit(int x) {
    return x & -x;
}

void update(int x) {
    while (x < c.size()) {
        ++c[x];
        x += lowbit(x);
    }
}

int query(int x) {
    int ans = 0;
    while (x > 0) {
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

int main() {
    int n, maxa = 0;
    cin >> n;
    vector<int> a(n);
    for (int& ai : a) {
        cin >> ai;
        if (maxa < ai) maxa = ai;
    }
    c.resize(maxa + 1, 0);
    long long ans = 0;
    for (int i = n - 1; i >= 0; --i) {
        ans += query(a[i] - 1);
        update(a[i]);
    }
    for (int i = 2; i < n; ++i) {
        ans = (ans + ans) % mod;
    }
    cout << ans;
}
// 64 位输出请用 printf("%lld")