Cho dãy số ~A~ gồm ~N~ phần tử là hoán vị của ~N~ số nguyên từ ~0~ đến ~N - 1~ và được đánh số lần lượt từ ~1~ đến ~N~. Phép biến đổi ~Swap(x)~ sẽ đổi chỗ ~A_{x}~ và ~A_{x + 1}~ ~(1 \leq x < N)~. Một hoán vị ~B~ gọi là đẹp nếu thỏa mãn ~2~ điều kiện sau:

1. Là hoán vị của ~N - 1~ số gồm các số từ ~1~ đến ~N - 1~.
2. Sau khi thực hiện lần lượt các phép biến đổi ~Swap(B_{1})~, ~Swap(B_{2})~, ..., ~Swap(B_{N - 1})~ trên dãy số ~A~ đã cho thì được dãy số mới là dãy tăng dần.

Yêu cầu: Hãy đếm số hoán vị đẹp.

Input

• Dòng ~1~: Số nguyên dương ~N~.
• Dòng ~2~: Gồm ~N~ số nguyên, là giá trị ban đầu của dãy số ~A~.

Output

• Phần dư khi chia số hoán vị đẹp cho ~10^{9} + 7~.

Giới hạn

~1 \leq N \leq 100~

~20\%~ số test ~N \leq 10~.

Sample Input

4
2 0 3 1

Sample Output

2

Note

• Dãy số ~A~ ban đầu là ~(2, 0, 3, 1)~.
• Các hoán vị được sinh ra là ~(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)~.
• Có ~2~ hoán vị đẹp là ~(1, 3, 2)~ và ~(3, 1, 2)~.