逆序对----找规律+快速幂 or 递推+矩阵快速幂

方法一：找规律+快速幂
假设需要构成长度为n的字符串，任取其中两个元素组成1 0，那么会有种选择方法是不一样的，对于长度为n的字符串，选择一种方法后，还会剩下 个字符，每个字符可以是0或1，那么就有种可能，所以可以推出答案式子
因为有个取模操作，所以除法要换成乘法，因为这题的公式可以抵消，所以不需要求逆元。

补充说明：求2关于质数mod的逆元可以根据费马小定理 除以2%mod等于乘以2^(mod-2)%mod

#include <cctype>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
const long long mod=1e9+7;
long long ksm(long long a, long long x) {
    long long res=1;
    while (x) {
        if (x&1) res=res*a%mod;
        a=a*a%mod;
        x>>=1;
    }
    return res;
}
int main() {
    long long n;
    cin>>n;
    if (n==0||n==1) cout<<0<<endl;
    else if (n==2) cout<<1<<endl;
    else {
        //求逆元
        //cout<<(n%mod)*((n-1)%mod)%mod*ksm(2,mod-2)%mod*ksm(2,n-2)%mod;
        cout<<(n%mod)*((n-1)%mod)%mod*ksm(2,n-3)%mod;
    }
    return 0;
}

方法二：递推+矩阵快速幂
比较好想，也是我第一次做的方法，递推式很好想，上图

推到这就行了，直接上矩阵快速幂即可

#include <cctype>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
const long long mod=1e9+7;
struct node {
    long long a[3][3];
    node() {
        memset(a,0,sizeof(a));
    }
};
node Mul(node n1, node n2) {
    node res;
    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {
            for (int k=0; k<3; k++) res.a[i][j]=(res.a[i][j]+n1.a[i][k]*n2.a[k][j]%mod)%mod;
        }
    }
    return res;
}
node solve(node n1, long long k) {
    node res;
    for (int i=0; i<3; i++) res.a[i][i]=1;
    while (k) {
        if (k&1) res=Mul(res,n1);
        k>>=1;
        n1=Mul(n1,n1);
    }
    return res;
}
int main() {
    long long n;
    cin>>n;
    if (n==0||n==1) cout<<0<<endl;
    else if (n==2) cout<<1<<endl;
    else {
        node n1;
        n1.a[0][0]=2;
        n1.a[0][1]=1;
        n1.a[0][2]=1;
        n1.a[1][0]=0;
        n1.a[1][1]=2;
        n1.a[1][2]=2;
        n1.a[2][0]=0;
        n1.a[2][1]=0;
        n1.a[2][2]=2;
        node res=solve(n1,n-2);
        long long ans=(res.a[0][0]+2*res.a[0][1]%mod+2*res.a[0][2]%mod)%mod;
        cout<<ans<<endl;
    }
    return 0;
}