Problem Statement

You are given a permutation $P$ of $(1,2,\dots,N)$. There is also a permutation $Q=(1,2,\dots,N)$ of $(1,2,\dots,N)$.

Perform the following operation on $Q$ for $i=1,2,\dots,N$ in this order.

• Remove $i$ from $Q$ and insert $i$ into any one position in $Q$.

Find the number, modulo $(10^9+7)$, of ways to perform $N$ operations such that $P$ and $Q$ are equal after all operations.

Constraints

• $1 \le N \le 5000$
• $P$ is a permutation of $(1,2,\dots,N)$.

Input

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

N
P_1 P_2 \dots P_N

Output

Print the answer.