#pragma comment(linker, "/STACK:10240000,10240000")

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstdlib>

 #include <cstring>

 #include <map>

 #include <queue>

 #include <deque>

 #include <cmath>

 #include <vector>

 #include <ctime>

 #include <cctype>

 #include <set>

 #include <bitset>

 #include <functional>

 #include <numeric>

 #include <stdexcept>

 #include <utility>

 using namespace std;

 #define mem0(a) memset(a, 0, sizeof(a))

 #define mem_1(a) memset(a, -1, sizeof(a))

 #define lson l, m, rt << 1

 #define rson m + 1, r, rt << 1 | 1

 #define define_m int m = (l + r) >> 1

 #define rep_up0(a, b) for (int a = 0; a < (b); a++)

 #define rep_up1(a, b) for (int a = 1; a <= (b); a++)

 #define rep_down0(a, b) for (int a = b - 1; a >= 0; a--)

 #define rep_down1(a, b) for (int a = b; a > 0; a--)

 #define all(a) (a).begin(), (a).end()

 #define lowbit(x) ((x) & (-(x)))

 #define constructInt4(name, a, b, c, d) name(int a = 0, int b = 0, int c = 0, int d = 0): a(a), b(b), c(c), d(d) {}

 #define constructInt3(name, a, b, c) name(int a = 0, int b = 0, int c = 0): a(a), b(b), c(c) {}

 #define constructInt2(name, a, b) name(int a = 0, int b = 0): a(a), b(b) {}

 #define pchr(a) putchar(a)

 #define pstr(a) printf("%s", a)

 #define sstr(a) scanf("%s", a)

 #define sint(a) scanf("%d", &a)

 #define sint2(a, b) scanf("%d%d", &a, &b)

 #define sint3(a, b, c) scanf("%d%d%d", &a, &b, &c)

 #define pint(a) printf("%d\n", a)

 #define test_print1(a) cout << "var1 = " << a << endl

 #define test_print2(a, b) cout << "var1 = " << a << ", var2 = " << b << endl

 #define test_print3(a, b, c) cout << "var1 = " << a << ", var2 = " << b << ", var3 = " << c << endl

 #define mp(a, b) make_pair(a, b)

 #define pb(a) push_back(a)

 typedef unsigned int uint;

 typedef long long LL;

 typedef pair<int, int> pii;

 typedef vector<int> vi;

 const int dx[] = {, , -, , , , -, -};

 const int dy[] = {-, , , , , -, , - };

 const int maxn = 1e8 + ;

 const int md = 1e9 + ;

 const int inf = 1e9 + ;

 const LL inf_L = 1e18 + ;

 const double pi = acos(-1.0);

 const double eps = 1e-;

 template<class T>T gcd(T a, T b){return b==?a:gcd(b,a%b);}

 template<class T>bool max_update(T &a,const T &b){if(b>a){a = b; return true;}return false;}

 template<class T>bool min_update(T &a,const T &b){if(b<a){a = b; return true;}return false;}

 template<class T>T condition(bool f, T a, T b){return f?a:b;}

 template<class T>void copy_arr(T a[], T b[], int n){rep_up0(i,n)a[i]=b[i];}

 int make_id(int x, int y, int n) { return x * n + y; }

 template<int mod>

 struct ModInt {

     const static int MD = mod;

     int x;

     ModInt(int x = ): x(x) { if (x < ) x += mod; }

     int get() { return x; }

     ModInt operator + (const ModInt &that) const { int x0 = x + that.x; return ModInt(x0 < MD? x0 : x0 - MD); }

     ModInt operator - (const ModInt &that) const { int x0 = x - that.x; return ModInt(x0 < MD? x0 + MD : x0); }

     ModInt operator * (const ModInt &that) const { return ModInt((long long)x * that.x % MD); }

     ModInt operator / (const ModInt &that) const { return *this * that.inverse(); }

     ModInt operator += (const ModInt &that) { x += that.x; if (x >= MD) x -= MD; }

     ModInt operator -= (const ModInt &that) { x -= that.x; if (x < ) x += MD; }

     ModInt operator *= (const ModInt &that) { x = (long long)x * that.x % MD; }

     ModInt operator /= (const ModInt &that) { *this = *this / that; }

     ModInt inverse() const {

         int a = x, b = MD, u = , v = ;

         while(b) {

             int t = a / b;

             a -= t * b; std::swap(a, b);

             u -= t * v; std::swap(u, v);

         }

         if(u < ) u += MD;

         return u;

     }

 };

 typedef ModInt<md> mint;

 mint dp[], fact[];

 int n, a[];

 bool vis[];

 void init() {

     fact[] = ;

     rep_up1(i, ) {

         dp[i] = dp[i - ] * i + fact[i - ] * i * (i - ) / ;

         fact[i] = fact[i - ] * i;

     }

 }

 int main() {

     //freopen("in.txt", "r", stdin);

     init();

     while (cin >> n) {

         rep_up0(i, n) sint(a[i]);

         mem0(vis);

         mint ans = ;

         rep_up0(i, n) {

             int c = ;

             rep_up0(j, i) {

                 for (int k = j + ; k < i; k ++) {

                     if (a[j] > a[k]) c ++;

                 }

             }

             rep_up1(j, a[i] - ) {

                 if (!vis[j]) {

                     ans += fact[n - i - ] * c;

                     rep_up0(k, i) {

                         if (a[k] > j) ans += fact[n - i - ];

                     }

                     int sum = ;

                     vis[j] = true;

                     rep_up1(k, n) {

                         if (!vis[k]) sum ++;

                         else ans += fact[n - i - ] * sum;

                     }

                     ans += dp[n - i - ];

                     vis[j] =false;

                 }

             }

             vis[a[i]] = true;

         }

         cout << ans.get() << endl;

     }

     return ;

 }