算是个水题。
虽然我打表以后直接去了oeis..

题目大意：
给定一个长度为n，问长度为n的01串中有多少个逆序对。
这里的逆序对为对于i<j,a[i]=1,a[j]=0
n<=1e18

思路：
数据范围很大，递推肯定是不行的。那么显然本题是一个公式题，或者需要矩阵优化的递推。
暴力打表很简单，可以发现能够得到一个公式的，先把公式贴下：
a[i]=i * (i-1) * (2^(i-3)) （i>=3）
a[1]=0
a[2]=1

这个公式，如果对着打表的结果推的话，应该不好推吧？？
我们利用数学知识来解决：
枚举任意两个位置，其中左边这个放1，右边位置放0。显然n个位置里，有C(2,n)种方案。
接下来的n-2个位置中，我们可以随便放0或1，一共有2^(n-2)种方案。
答案就是C(2,n)*2^(n-2)
知道公式以后，剩下的就是快速幂了。

代码：

#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
long long n;
long long quick(long long a,long long b){
    long long ans=1;
    while(b){
        if(b%2)ans=ans*a%mod;
        a=a*a%mod;
        b=b/2;
    }
    return ans%mod;
}
int main()
{
    cin>>n;
    if(n==1)cout<<0<<endl;
    else if(n==2)cout<<1<<endl;
    else {
        long long ans=(n%mod)*((n-1)%mod);
        ans=ans%mod;
        ans=ans*quick(2,n-3)%mod;
        cout<<ans%mod<<endl;
    }
    return 0;
}