#include <stdio.h>
#define swap(x, y) (x ^= y, y ^= x, x ^= y)
const int MOD = 1000000007;
int n, ar[100010], lim[100010];
int bigmod(int x, unsigned long long int n){
if (!n) return 1;
if (n == 1) return (x);
unsigned long long int res = bigmod(x, n / 2);
res = (res * res) % MOD;
if (n % 2) res = (res * x) % MOD;
return (res);
}
int main(){
int i, j;
while (scanf("%d", &n
) != EOF
){ for (i = 0; i < n; i++){
lim[i] = n;
}
unsigned long long int res = 1;
for (i = 0; i < n; i++){
if (lim[i] > i){
int c, d, x, y, counter = 0;
for (j = i; j < lim[i]; j++){
if (i == j) x = y = ar[j], c = d = j;
if (ar[j] < x) x = ar[j], c = j;
if (ar[j] > y) y = ar[j], d = j;
if (i != j) res = (res * (y - x)) % MOD;
counter++;
}
if (counter < 2) continue;
if (c > d) swap(c, d);
unsigned long long int p = 0, q = 0, z = 0;
p = (lim[i] - d);
q = (c - i);
z = (p * q);
res = (res * (bigmod(y - x, z))) % MOD;
for (j = i + 1; j <= c; j++) lim[j] = d;
}
}
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiAKI2RlZmluZSBzd2FwKHgsIHkpICh4IF49IHksIHkgXj0geCwgeCBePSB5KQogCmNvbnN0IGludCBNT0QgPSAxMDAwMDAwMDA3OwogCmludCBuLCBhclsxMDAwMTBdLCBsaW1bMTAwMDEwXTsKIAppbnQgYmlnbW9kKGludCB4LCB1bnNpZ25lZCBsb25nIGxvbmcgaW50IG4pewogICAgaWYgKCFuKSByZXR1cm4gMTsKICAgIGlmIChuID09IDEpIHJldHVybiAoeCk7CiAgICB1bnNpZ25lZCBsb25nIGxvbmcgaW50IHJlcyA9IGJpZ21vZCh4LCBuIC8gMik7CiAgICByZXMgPSAocmVzICogcmVzKSAlIE1PRDsKICAgIGlmIChuICUgMikgcmVzID0gKHJlcyAqIHgpICUgTU9EOwogICAgcmV0dXJuIChyZXMpOwp9CiAKaW50IG1haW4oKXsKICAgIGludCBpLCBqOwogCiAgICB3aGlsZSAoc2NhbmYoIiVkIiwgJm4pICE9IEVPRil7CiAgICAgICAgZm9yIChpID0gMDsgaSA8IG47IGkrKyl7CiAgICAgICAgICAgIHNjYW5mKCIlZCIsICZhcltpXSk7CiAgICAgICAgICAgIGxpbVtpXSA9IG47CiAgICAgICAgfQogCiAgICAgICAgdW5zaWduZWQgbG9uZyBsb25nIGludCByZXMgPSAxOwogICAgICAgIGZvciAoaSA9IDA7IGkgPCBuOyBpKyspewogICAgICAgICAgICBpZiAobGltW2ldID4gaSl7CiAgICAgICAgICAgICAgICBpbnQgYywgZCwgeCwgeSwgY291bnRlciA9IDA7CiAgICAgICAgICAgICAgICBmb3IgKGogPSBpOyBqIDwgbGltW2ldOyBqKyspewogICAgICAgICAgICAgICAgICAgIGlmIChpID09IGopIHggPSB5ID0gYXJbal0sIGMgPSBkID0gajsKICAgICAgICAgICAgICAgICAgICBpZiAoYXJbal0gPCB4KSB4ID0gYXJbal0sIGMgPSBqOwogICAgICAgICAgICAgICAgICAgIGlmIChhcltqXSA+IHkpIHkgPSBhcltqXSwgZCA9IGo7CiAgICAgICAgICAgICAgICAgICAgaWYgKGkgIT0gaikgcmVzID0gKHJlcyAqICh5IC0geCkpICUgTU9EOwogICAgICAgICAgICAgICAgICAgIGNvdW50ZXIrKzsKICAgICAgICAgICAgICAgIH0KIAogICAgICAgICAgICAgICAgaWYgKGNvdW50ZXIgPCAyKSBjb250aW51ZTsKICAgICAgICAgICAgICAgIGlmIChjID4gZCkgc3dhcChjLCBkKTsKIAogICAgICAgICAgICAgICAgdW5zaWduZWQgbG9uZyBsb25nIGludCBwID0gMCwgcSA9IDAsIHogPSAwOwogICAgICAgICAgICAgICAgcCA9IChsaW1baV0gLSBkKTsKICAgICAgICAgICAgICAgIHEgPSAoYyAtIGkpOwogICAgICAgICAgICAgICAgeiA9IChwICogcSk7CiAgICAgICAgICAgICAgICByZXMgPSAocmVzICogKGJpZ21vZCh5IC0geCwgeikpKSAlIE1PRDsKICAgICAgICAgICAgICAgIGZvciAoaiA9IGkgKyAxOyBqIDw9IGM7IGorKykgbGltW2pdID0gZDsKICAgICAgICAgICAgfQogICAgICAgIH0KIAogICAgICAgIHByaW50ZigiJWxsdVxuIiwgcmVzKTsKICAgIH0KICAgIHJldHVybiAwOwp9