C++ code :
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll ;
ll sum5(ll x,ll y){
if(x<=y){
return (abs(y-x) + 1);
}
return 0 ;
}
ll sum(ll x,ll y){
if(x<=y){
return (((y*(y+1)/2)) - (((x-1)*x)/2)) ;
}
return 0 ;
}
ll vv = 1e9 + 7 ;
int main() {
ll n,m ;
unordered_map <ll,ll> gg ;
cin>>n>>m ;
ll b[200005]={0};
ll i = 1 ; ll sum = 0;
while(i<=m){
cin>>b[i] ;
sum = sum + b[i] ;
i++;
}
sort(b+1,b+m+1);
//vector <ll>
ll ss = 0 ;
vector <ll> T[200005] ;
i = 1 ;
while(i<=m){
ll ans = 0 ;
if(i==1){
ll v2 = b[m] ;
ll uu = b[i] ;
ll ds = n - b[m] + b[i] ;
ds++;
//ds--->n ----- (ds-1)
//ans = sum5(ds,n)*(ds-1)*b[i];
//ans = ans + sum(1,ds-1)*b[i] ;
T[ds].push_back(b[i]);
gg[b[i]] = ds - 1 ;
}
else {
ll v2 = b[i-1] ;
ll uu = b[i] ;
ll ds = b[i] - b[i-1] ;
ds++;
//cout<<ds<<" "<<n ;
//cout<<"\n";
//ds--->n ----- (ds-1)
//ans = sum5(ds,n)*(ds-1)*b[i];
//ans = ans + sum(1,ds-1)*b[i] ;
T[ds].push_back(b[i]);
gg[b[i]] = ds - 1 ;
}
//cout<<ans ;
//cout<<"\n";
i++;
}
ll x = 0 ;
ll y = 0 ;
ll y55 = 0 ;
ll tt = 1 ; ll rr = 1 ;
while(tt<=n){
x = sum*(tt);
for(auto uu : T[tt]){
y = y + uu ;
y55 = y55 + uu*gg[uu] ;
}
x = x - y*(tt) ;
//cout<<(x+y55);
//cout<<"\n";
rr = ((rr%vv)*((x%vv+y55%vv)%vv))%vv;
tt++;
}
cout<<rr ;
return 0 ;
}