class segtree: def __init__(self,n): self.size=1 while self.size1: x//=2 self.dat[x]=(self.dat[2*x]+self.dat[2*x+1]) def querry(self,u,v): u+=self.size v+=self.size score=0 while u0: if n&1: ans*=w ans%=mod w**=2 w%=mod n//=2 u2[i]=ans def ncm(x,y): ans=u[x] ans*=u2[y] ans%=mod ans*=u2[x-y] ans%=mod return ans Z0=segtree(N) L=[] for i in range(N): L.append((A[i],i)) L.sort() result=0 for i in range(N): pos=L[i][1] x1=Z0.querry(0,pos) x2=Z0.querry(pos+1,N) y1=pos-x1 y2=(N-1-pos)-x2 w=ncm(x1+y2,x1)*ncm(x2+y1,y1) w%=mod result+=w result%=mod Z0.update(pos,1) print(result)