Theo dõi tiến độ

Cho một cây $T$ gồm $n$ đỉnh được đánh số từ $1$ đến $n$, biểu diễn bằng ma trận kề $a[1\dots n][1\dots n]$. Người ta chạy đoạn mã giả sau trên cây đó:

used[1 ... n] = {0, ..., 0};

procedure dfs(v):
    print v;
    used[v] = 1;
    for i = 1, 2, ..., n:
        if (a[v][i] == 1 and used[i] == 0):
            dfs(i);

dfs(1);

Kết quả in ra là một dãy $n$ số, chính là thứ tự các đỉnh được thăm.

Cho trước dãy $b_1,b_2,\dots ,b_n$. Hãy đếm số cây $T$ khác nhau sao cho đoạn mã giả trên in ra đúng dãy $b$.

Hai cây $n$ đỉnh được coi là khác nhau nếu ma trận kề của chúng khác nhau, tức là tồn tại cặp $(i,j)$ với $1\le i,j\le n$ mà $a_1[i][j]\ne a_2[i][j]$.

Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa số nguyên dương $n$ là độ dài của dãy $b$.
• Dòng thứ hai chứa $n$ số nguyên dương $b_1,b_2,\dots ,b_n$.

Dữ liệu ra

Một số nguyên duy nhất: số cây thoả mãn, lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le n\le 500$
• $1\le b_i\le n$
• $b$ là một hoán vị của $1,2,\dots ,n$
• $b_1=1$

Ví dụ