#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3F3F3F3F
const int B = 1e2 + 5;
const int MXN = 1e4 + 5;
const int mod = 1e6 + 7;
int dp[B][MXN];
int bl[B][MXN];
int cur[MXN], nw[MXN];
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int a[n + 1];
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = n; i >= 1; i--)
{
for (int j = 1; j <= n; j++)
{
if (i == n) nw[j] = 1;
else nw[j] = cur[j + 1] + (cur[j] * j) % mod;
}
for (int j = 1; j <= n; j++) cur[j] = nw[j];
if (i % B == 0) for (int j = 1; j <= n; j++) bl[i / B][j] = cur[j];
}
if (B > n) for (int i = 1; i <= n; i++) dp[n % B][i] = 1;
else for (int i = 1; i <= n; i++) dp[0][i] = bl[1][i];
for (int i = min(B, n) - 1; i >= 1; i--)
{
for (int j = 1; j <= n; j++)
{
dp[i % B][j] = (dp[(i + 1) % B][j + 1] + (dp[(i + 1) % B][j] * j)) % mod;
}
}
int val = a[1], res = 0;
for (int i = 1; i < n; i++)
{
val = max(val, a[i]);
if (i % B == 0)
{
if ((i / B + 1) * B > n) for (int j = 1; j <= n; j++) dp[n % B][j] = 1;
else for (int j = 1; j <= n; j++) dp[0][j] = bl[i / B + 1][j];
for (int k = min((i / B + 1) * B, n) - 1; k > i; k--)
{
for (int j = 1; j <= n; j++)
{
dp[k % B][j] = (dp[(k + 1) % B][j + 1] + (dp[(k + 1) % B][j] * j)) % mod;
}
}
}
res = (res + (((a[i + 1] - 1) * dp[(i + 1) % B][val]) % mod));
}
cout << (res + 1) % mod << '\n';
}
