#include <bits/stdc++.h>
#include <unistd.h>
#define ll long long
#define inf 1000000007
#define inf16 0x3f3f3f3f
#define INF 1000000000000000007LL
#define VI vector<int>
#define VPII vector<pair<int, int> >
#define VLL vector<ll>
#define PII pair<int, int>
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define endl '\n'
#define ALL(c) (c).begin(), (c).end()
using namespace std;

#define int ll
const int mod = 1e9+7;
const int N = 1<<18;

int n, ans, all = 1;

int w[N];
int A[N];

int p0[N];
int p1[N];
int moge[N];

int fpow(int a, int b)
{
	int res = 1;

	while(b)
	{
		if(b&1)
			res = res*a%mod;

		a = a*a%mod;
		b /= 2;
	}

	return res;
}

/*int f(int a, int b)
{
	if(a+1<moge[b])
		return 0;
	else
		return all*p1[b]%mod*p0[a]%mod;
}*/

struct tree
{
	int load[2*N];

	void insert(int a, int v)
	{
		a += N;

		while(a)
		{
			load[a] += v;
			load[a] %= mod;
			a /= 2;
		}
	}

	int query(int a, int b)
	{
		if(a>b)
			return 0;

		a += N;
		b += N;

		int res = load[a];

		if(a!=b)
		{
			res += load[b];
			res %= mod;
		}

		while(a<b-1)
		{
			if(a%2==0)
			{
				res += load[a+1];
				res %= mod;
			}

			if(b%2==1)
			{
				res += load[b-1];
				res %= mod;
			}

			a /= 2;
			b /= 2;
		}

		return res;
	}
};

tree T, cnt;

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);

	cin >> n;

	for(int i = 1; i <= n; ++i)
	{
		cin >> A[i];
		++w[A[i]];
	}

	for(int i = n; i >= 1; --i)
	{
		w[i] += w[i+1];
	}

	for(int i = n; i >= 1; --i)
	{
		w[i] -= n-i;
		all = all*w[i]%mod;
	}

	p0[0] = p1[0] = 1;
	moge[0] = 1;

	for(int i = 1; i <= n; ++i)
	{
		p0[i] = p0[i-1]*w[i]%mod;
		p1[i] = p1[i-1]*(w[i]-1)%mod;

		if(p1[i]==0)
		{
			p0[i] = p1[i] = 1;
			moge[i] = i;
		}
		else
			moge[i] = moge[i-1];
	}

	if(!all)
	{
		cout << 0 << endl;
		return 0;
	}

	for(int i = 1; i <= n; ++i)
	{
		int z0 = fpow(p1[i], mod-2)*p0[i]%mod;
		int z1 = fpow(p0[i], mod-2)*p1[i]%mod;
		p0[i] = z0;
		p1[i] = z1;
	}

	for(int i = 1; i <= n; ++i)
	{
		ans += all*cnt.query(A[i], n)%mod;
		ans += p1[A[i]]*T.query(moge[A[i]], A[i]-1)%mod;

		ans %= mod;

		T.insert(A[i], all*p0[A[i]]%mod*fpow(2, mod-2)%mod);
		cnt.insert(A[i], 1);
	}

	memset(T.load, 0, sizeof T.load);

	for(int i = n; i >= 1; --i)
	{
		ans += p1[A[i]]*T.query(moge[A[i]], A[i])%mod;

		ans %= mod;

		T.insert(A[i], -all*p0[A[i]]%mod*fpow(2, mod-2)%mod);
	}

	ans += mod;
	ans %= mod;

	cout << ans << endl;
}
### Prompt

Create a solution in Cpp for the following problem:

Snuke has an integer sequence A whose length is N. He likes permutations of (1, 2, ..., N), P, that satisfy the following condition:

* P_i \leq A_i for all i ( 1 \leq i \leq N ).



Snuke is interested in the inversion numbers of such permutations. Find the sum of the inversion numbers over all permutations that satisfy the condition. Since this can be extremely large, compute the sum modulo 10^9+7.

Constraints

* 1 \leq N \leq 2 \times 10^5
* 1 \leq A_i \leq N ( 1 \leq i \leq N )
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_1 A_2 ... A_N


Output

Print the sum of the inversion numbers over all permutations that satisfy the condition.

Examples

Input

3
2 3 3


Output

4


Input

6
4 2 5 1 6 3


Output

7


Input

5
4 4 4 4 4


Output

0


Input

30
22 30 15 20 10 29 11 29 28 11 26 10 18 28 22 5 29 16 24 24 27 10 21 30 29 19 28 27 18 23


Output

848414012

### Response

```cpp
#include <bits/stdc++.h>
#include <unistd.h>
#define ll long long
#define inf 1000000007
#define inf16 0x3f3f3f3f
#define INF 1000000000000000007LL
#define VI vector<int>
#define VPII vector<pair<int, int> >
#define VLL vector<ll>
#define PII pair<int, int>
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define endl '\n'
#define ALL(c) (c).begin(), (c).end()
using namespace std;

#define int ll
const int mod = 1e9+7;
const int N = 1<<18;

int n, ans, all = 1;

int w[N];
int A[N];

int p0[N];
int p1[N];
int moge[N];

int fpow(int a, int b)
{
	int res = 1;

	while(b)
	{
		if(b&1)
			res = res*a%mod;

		a = a*a%mod;
		b /= 2;
	}

	return res;
}

/*int f(int a, int b)
{
	if(a+1<moge[b])
		return 0;
	else
		return all*p1[b]%mod*p0[a]%mod;
}*/

struct tree
{
	int load[2*N];

	void insert(int a, int v)
	{
		a += N;

		while(a)
		{
			load[a] += v;
			load[a] %= mod;
			a /= 2;
		}
	}

	int query(int a, int b)
	{
		if(a>b)
			return 0;

		a += N;
		b += N;

		int res = load[a];

		if(a!=b)
		{
			res += load[b];
			res %= mod;
		}

		while(a<b-1)
		{
			if(a%2==0)
			{
				res += load[a+1];
				res %= mod;
			}

			if(b%2==1)
			{
				res += load[b-1];
				res %= mod;
			}

			a /= 2;
			b /= 2;
		}

		return res;
	}
};

tree T, cnt;

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);

	cin >> n;

	for(int i = 1; i <= n; ++i)
	{
		cin >> A[i];
		++w[A[i]];
	}

	for(int i = n; i >= 1; --i)
	{
		w[i] += w[i+1];
	}

	for(int i = n; i >= 1; --i)
	{
		w[i] -= n-i;
		all = all*w[i]%mod;
	}

	p0[0] = p1[0] = 1;
	moge[0] = 1;

	for(int i = 1; i <= n; ++i)
	{
		p0[i] = p0[i-1]*w[i]%mod;
		p1[i] = p1[i-1]*(w[i]-1)%mod;

		if(p1[i]==0)
		{
			p0[i] = p1[i] = 1;
			moge[i] = i;
		}
		else
			moge[i] = moge[i-1];
	}

	if(!all)
	{
		cout << 0 << endl;
		return 0;
	}

	for(int i = 1; i <= n; ++i)
	{
		int z0 = fpow(p1[i], mod-2)*p0[i]%mod;
		int z1 = fpow(p0[i], mod-2)*p1[i]%mod;
		p0[i] = z0;
		p1[i] = z1;
	}

	for(int i = 1; i <= n; ++i)
	{
		ans += all*cnt.query(A[i], n)%mod;
		ans += p1[A[i]]*T.query(moge[A[i]], A[i]-1)%mod;

		ans %= mod;

		T.insert(A[i], all*p0[A[i]]%mod*fpow(2, mod-2)%mod);
		cnt.insert(A[i], 1);
	}

	memset(T.load, 0, sizeof T.load);

	for(int i = n; i >= 1; --i)
	{
		ans += p1[A[i]]*T.query(moge[A[i]], A[i])%mod;

		ans %= mod;

		T.insert(A[i], -all*p0[A[i]]%mod*fpow(2, mod-2)%mod);
	}

	ans += mod;
	ans %= mod;

	cout << ans << endl;
}
```