Do tình hình dịch bệnh Covid-19 đang diễn biến phức tạp, các biện pháp giãn cách xã hội được tiến hành, bao gồm việc hạn chế tụ tập đông đúc. Siro đành phải tạm hoãn việc chơi bóng đá với những người bạn. Trong lúc buồn chán, cậu đã nghĩ ra trò chơi "PERTATS" như sau:

Người chơi sẽ được nhận một hoán vị ~p~ gồm ~n~ phần tử ~p_1, p_2, . . ., p_n~. Sau đó, người chơi sẽ thực hiện một phép biến đổi gồm hai bước sau:

• Bước ~1~: Chọn ra ~k (k > 0)~ cặp số nguyên ~(l_i, r_i)~ sao cho ~1 \le l_1 < r_1 < l_2 < r_2 < ... < l_k < r_k \le n~.
• Bước ~2~: Với mỗi cặp chỉ số ~(l_i, r_i)~ được chọn, người chơi cần sắp xếp đoạn con từ vị trí ~l_i~ đến ~r_i~ của hoán vị ~p~ theo thứ tự tăng dần.

Ví dụ, với hoán vị ~p = [6, 2, 5, 4, 3, 1]~:

• Nếu chọn hai cặp số nguyên ~(1, 3), (5, 6)~ thì hoán vị nhận được sau phép biến đổi là ~[2, 5, 6, 4, 1, 3]~
• Nếu chọn một cặp số nguyên ~(2, 5)~ thì hoán vị nhận được sau phép biến đổi là ~[6, 2, 5, 4, 3, 1]~

Sau khi đã chơi qua trò chơi trên nhiều lần, Siro tự hỏi rằng: với một hoán vị ~p~ cho trước, nếu xét tất cả cách chọn ở bước ~1~ thì có thể nhận được bao nhiêu hoán vị khác nhau. Do số hoán vị có thể rất lớn, Siro chỉ muốn biết đáp án sau khi chia lấy phần dư cho ~10^9 + 7~.

Input

• Dòng đầu ghi số nguyên dương ~n (1 \le n \le 5000)~;
• Dòng thứ hai ghi ~n~ số nguyên dương là hoán vị ~p (1 \le p_i \ne p_j \le n)~ với ~(1 \le i \ne j \le n)~.

Output

• Đáp án cho câu hỏi mà Siro đã đặt ra.

Sample

Input #1

3
1 2 3

Output #1

1

Input #2

4
3 2 4 1

Output #2

6

Input #3

12
4 1 9 5 3 8 7 10 6 2 12 11

Output #3

300

Hint

Giải thích #1:

• Với ~K = 0~, không chọn được cặp ~(l, r)~ nào, hoán vị nhận được là ~[1, 2, 3]~
• Với ~K = 1~, chọn cặp ~l_1 = 1, r_1 = 2~ ta nhận được hoán vị ~[1, 2, 3]~
• Với ~K = 1~, chọn cặp ~l_1 = 2, r_1 = 3~ ta nhận được hoán vị ~[1, 2, 3]~
• Với ~K = 1~, chọn cặp ~l_1 = 1, r_1 = 3~ ta nhận được hoán vị ~[1, 2, 3]~

Chỉ tìm được ~1~ hoán vị: ~[1, 2, 3]~