#include using namespace std; #define ALL(x) x.begin(),x.end() #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<bool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b ostream &operator<<(ostream &os,const pair&p){ os< ostream &operator<<(ostream &os,const vector&v){ for(int i=0;i<(int)v.size();i++) os< istream &operator>>(istream &is,pair&p){ is>>p.first>>p.second; return is; } template istream &operator>>(istream &is,vector&v){ for(T &x:v)is>>x; return is; } template struct BinaryIndexedTree{ vector data; BinaryIndexedTree(int sz){ data.assign(sz+1, 0); } // 区間[0,k]の合計 sum(v[0]~v[k]) T sum(int k){ T ret=0; for(++k;k>0;k-=(k&-k)) ret+=data[k]; return ret; } // v[a]+=x void add(int k,T x){ for(++k;k0;k>>=1){ if(x+k<=data.size()&&data[x+k] v){ int n=v.size(); if(n<=1){ return 0; } int vmax=*max_element(ALL(v)); BinaryIndexedTree bit(vmax+1); ll ret=0; rep(i,n){ ret+=bit.sum(vmax)-bit.sum(v[i]); bit.add(v[i],1); } return ret; } template struct SegmentTree{ using F=function; int sz; vector seg; const F f; const Monoid gen; SegmentTree(int n,const F f,const Monoid &gen):f(f),gen(gen){ sz=1; while(sz0;k--) seg[k]=f(seg[2*k],seg[2*k+1]); } void update(int k,const Monoid &x){ k+=sz; seg[k]=x; while(k>>=1) seg[k]=f(seg[2*k],seg[2*k+1]); } // [a,b) Monoid query(int a,int b){ Monoid L=gen,R=gen; for(a+=sz,b+=sz;a>=1,b>>=1){ if(a&1) L=f(L,seg[a++]); if(b&1) R=f(seg[--b],R); } return f(L,R); } Monoid operator[](const int &k)const { return seg[k+sz]; } }; int f(int a,int b){ return a+b; } template struct ModInt{ long long x; ModInt():x(0){} ModInt(long long y):x(y>=0?y%Mod:(Mod-(-y)%Mod)%Mod){} ModInt &operator+=(const ModInt &p){ if((x+=p.x)>=Mod) x-=Mod; return *this; } ModInt &operator-=(const ModInt &p){ if((x+=Mod-p.x)>=Mod)x-=Mod; return *this; } ModInt &operator*=(const ModInt &p){ x=(int)(1ll*x*p.x%Mod); return *this; } ModInt &operator/=(const ModInt &p){ (*this)*=p.inverse(); return *this; } ModInt operator-()const{return ModInt(x);} ModInt operator+(const ModInt &p)const{return ModInt(*this)+=p;} ModInt operator-(const ModInt &p)const{return ModInt(*this)-=p;} ModInt operator*(const ModInt &p)const{return ModInt(*this)*=p;} ModInt operator/(const ModInt &p)const{return ModInt(*this)/=p;} ModInt operator==(const ModInt &p)const{return x==p.x;} ModInt operator!=(const ModInt &p)const{return x!=p.x;} ModInt inverse()const{ int a=x,b=Mod,u=1,v=0,t; while(b>0){ t=a/b; swap(a-=t*b,b);swap(u-=t*v,v); } return ModInt(u); } ModInt pow(long long n)const{ ModInt ret(1),mul(x); while(n>0){ if(n&1) ret*=mul; mul*=mul;n>>=1; } return ret; } friend ostream &operator<<(ostream &os,const ModInt &p){return os<>(istream &is,ModInt &a){long long t;is>>t;a=ModInt(t);return (is);} static int get_mod(){return Mod;} }; using mint=ModInt; template struct comcalc{ vector fact,finv,inv; comcalc():fact(MAX),finv(MAX),inv(MAX){ fact[0]=mint(1),fact[1]=mint(1),finv[0]=mint(1),finv[1]=mint(1),inv[1]=mint(1); for(int i=2;in-r) r=n-r; if(r==0) return 1; mint a=1,b=mint(fact_mod(r)).inverse(); for(int i=0;i; signed main(){ cominit F; int n;cin>>n; vector a(n); cin>>a; map id; { auto comp=a; sort(ALL(comp)); comp.erase(unique(ALL(comp)),comp.end()); rep(i,n) a[i]=lower_bound(ALL(comp),a[i])-begin(comp); } ll IN=inversion_number(a); mint inm=mint(IN); mint alm=1; for(int i=1;i<=n;i++) alm*=F.com(n,i); mint dome=0; for(int i=2;i<=n;i++){ dome+=inm/F.com(n,i)*F.com(n-2,i-2); } dome*=alm; mint fore=0; // 係数は転倒数じゃなくてsum vector v(n,0); rep(i,n)v[a[i]]++; vector sum(n+1,0); rep(i,n)sum[i+1]=sum[i]+v[i]; mint alp=0; rep(i,n){ alp+=mint(v[i])*mint(sum[i]); } mint ri=0; for(int i=n;i>0;i--){ fore+=ri*F.com(n-1,i-1)/F.com(n,i); ri+=F.com(n-1,i-1)/F.com(n,i); } fore*=alp; fore*=alm; cout<