You are developing frog-shaped robots, and decided to race them against each other.

First, you placed N robots onto a number line. These robots are numbered 1 through N. The current coordinate of robot i is x_i. Here, all x_i are integers, and 0 < x_1 < x_2 < ... < x_N.

You will repeatedly perform the following operation:

* Select a robot on the number line. Let the coordinate of the robot be x. Select the destination coordinate, either x-1 or x-2, that is not occupied by another robot. The robot now jumps to the selected coordinate.



When the coordinate of a robot becomes 0 or less, the robot is considered finished and will be removed from the number line immediately. You will repeat the operation until all the robots finish the race.

Depending on your choice in the operation, the N robots can finish the race in different orders. In how many different orders can the N robots finish the race? Find the answer modulo 10^9+7.

Constraints

* 2 ≤ N ≤ 10^5
* x_i is an integer.
* 0 < x_1 < x_2 < ... < x_N ≤ 10^9

Input

The input is given from Standard Input in the following format:


N
x_1 x_2 ... x_N


Output

Print the number of the different orders in which the N robots can finish the race, modulo 10^9+7.

Examples

Input

3
1 2 3


Output

4


Input

3
2 3 4


Output

6


Input

8
1 2 3 5 7 11 13 17


Output

10080


Input

13
4 6 8 9 10 12 14 15 16 18 20 21 22


Output

311014372
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringJoiner;
import java.util.StringTokenizer;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;

public class Main {
    static In in = new In();
    static Out out = new Out();
    static long mod = 1000000007;
    static long inf = 0xfffffffffffffffL;

    void solve() {
        int n = in.nextInt();
        int[] x = in.nextIntArray(n);
        int last = -1;
        long ans = 1;
        int rem = n;
        for (int i = 0; i < n; i++) {
            if (last + 1 >= x[i]) {
                ans = ans * (i + rem - n + 1) % mod;
                rem--;
            } else {
                last += 2;
            }
        }
        Combination combination = new Combination();
        out.println(ans * combination.fact(rem) % mod);
    }

    static class Combination {
        private List<Long> fact = new ArrayList<>();
        private List<Long> invFact = new ArrayList<>();

        private void build(int n) {
            if (fact.isEmpty()) {
                fact.add(1L);
                invFact.add(1L);
            }
            for (int i = fact.size(); i <= n; i++) {
                fact.add(fact.get(i - 1) * i % mod);
                invFact.add(pow(fact.get(i), mod - 2));
            }
        }

        private void rangeCheck(long n, long r) {
            if (n < r) {
                throw new IllegalArgumentException("n < r");
            }
            if (n < 0) {
                throw new IllegalArgumentException("n < 0");
            }
            if (r < 0) {
                throw new IllegalArgumentException("r < 0");
            }
        }

        long fact(int n) {
            build(n);
            return fact.get(n);
        }

        long invFact(int n) {
            build(n);
            return invFact.get(n);
        }

        long comb(int n, int r) {
            rangeCheck(n, r);
            return fact(n) * invFact(r) % mod * invFact(n - r) % mod;
        }

        long comb(long n, long r) {
            rangeCheck(n, r);
            r = Math.min(r, n - r);
            long x = 1, y = 1;
            for (long i = 1; i <= r; i++) {
                x = x * (n - r + i) % mod;
                y = y * i % mod;
            }
            return x * inv(y) % mod;
        }

        long perm(int n, int r) {
            rangeCheck(n, r);
            return fact(n) * invFact(n - r) % mod;
        }

        long perm(long n, long r) {
            rangeCheck(n, r);
            long x = 1;
            for (long i = 1; i <= r; i++) {
                x = x * (n - r + i) % mod;
            }
            return x;
        }

        long homo(int n, int r) {
            rangeCheck(n, r);
            return r == 0 ? 1 : comb(n + r - 1, r);
        }

        long homo(long n, long r) {
            rangeCheck(n, r);
            return r == 0 ? 1 : comb(n + r - 1, r);
        }

        long inv(long a) {
            return pow(a, mod - 2);
        }

        long pow(long a, long b) {
            long x = 1;
            while (b > 0) {
                if (b % 2 == 1) {
                    x = x * a % mod;
                    b--;
                } else {
                    a = a * a % mod;
                    b /= 2;
                }
            }
            return x;
        }
    }

    public static void main(String[]$) {
        new Main().solve();
        out.flush();
    }
}

class In {
    private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 0x10000);
    private StringTokenizer tokenizer;

    String next() {
        try {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
        } catch (IOException ignored) {
        }
        return tokenizer.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    char[][] nextCharArray(int n, int m) {
        char[][] a = new char[n][m];
        for (int i = 0; i < n; i++) {
            a[i] = next().toCharArray();
        }
        return a;
    }

    int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        return a;
    }

    int[] nextIntArray(int n, IntUnaryOperator op) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = op.applyAsInt(nextInt());
        }
        return a;
    }

    long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextLong();
        }
        return a;
    }

    long[] nextLongArray(int n, LongUnaryOperator op) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = op.applyAsLong(nextLong());
        }
        return a;
    }
}

class Out {
    private PrintWriter out = new PrintWriter(System.out);
    boolean autoFlush = false;

    void println(Object... a) {
        StringJoiner joiner = new StringJoiner(" ");
        for (Object obj : a) {
            joiner.add(String.valueOf(obj));
        }
        out.println(joiner);
        if (autoFlush) {
            out.flush();
        }
    }

    void println(int[] a) {
        StringJoiner joiner = new StringJoiner(" ");
        for (int i : a) {
            joiner.add(Integer.toString(i));
        }
        out.println(joiner);
        if (autoFlush) {
            out.flush();
        }
    }

    void println(long[] a) {
        StringJoiner joiner = new StringJoiner(" ");
        for (long i : a) {
            joiner.add(Long.toString(i));
        }
        out.println(joiner);
        if (autoFlush) {
            out.flush();
        }
    }

    void flush() {
        out.flush();
    }
}
