Guest User

Untitled

a guest
Feb 17th, 2018
106
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* "Sahand Alitanloo" */
  2. #include <bits/stdc++.h>
  3. #define F first
  4. #define S second
  5. #define fast() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
  6. #define per(i) cout<<fixed<<setprecision(i)
  7. #define pb push_back
  8. #define all(v) begin(v),end(v)
  9. #define endl '\n'
  10. using namespace std;
  11. typedef pair<int,int> pii;
  12. typedef long double ld;
  13. typedef long long ll;
  14. const int MAX_N = 1e6+10;
  15. const ll mod = 1e9+7;
  16. const ll INF = 1e9;
  17. inline ll bpow(ll t,ll n){ll ans=1;while(n>0){if(n&1)ans=(ans*t)%mod;t=(t*t)%mod,n>>=1;}return ans;}
  18.  
  19. ll fact[MAX_N],ifact[MAX_N];
  20. inline ll divmod(ll n,ll k){return n*bpow(k,mod-2)%mod;}
  21. inline ll c(ll n,ll k){if(k>n||k<0||n<0)return 0;return (fact[n]*ifact[k]%mod*ifact[n-k])%mod;}
  22. inline void get_fact(){fact[0]=1;ifact[0]=1;for(ll i=1;i<MAX_N;i++)fact[i]=(fact[i-1]*i)%mod,ifact[i]=bpow(fact[i],mod-2);}
  23.  
  24. ll a[MAX_N];
  25. ll les[MAX_N];
  26. ll more[MAX_N];
  27. main(){
  28. fast();per(0);
  29. get_fact();
  30. ll n;scanf("%lld", &n);
  31. for(ll i=1;i<=n;i++)
  32. scanf("%lld", &a[i]);
  33. sort(a+1,a+n+1);
  34. for(ll i=1;i<=n;i++)
  35. les[i]=lower_bound(a+1,a+i,a[i])-a-1;
  36. ll ans=0;
  37. for(ll i=1;i<=n;i++){
  38. ll sum=(a[i]!=a[n])?divmod(fact[n],n-les[i]):0;
  39. sum*=a[i];
  40. sum%=mod;
  41. ans+=sum;
  42. ans%=mod;
  43. }
  44. cout<<ans;
  45. }
RAW Paste Data