Hasan has \(n\) balls placed on a line, the \(i^{th}\) ball is initially located in the \(p_i^{th}\) cell. No two balls can ever occupy a single cell.

There are \(m\) robots and a robot \(x \rightarrow y\) can go from cell \(x\) to cell \(y\) and push all the balls on their way. If one ball stands in the way of another ball, then it's also pushed. E. g. if you apply robot \(1 \rightarrow 4\) to \(\texttt{1011000001}\) (1-based index) you'll get \(\texttt{0000111001}\). (Here \(\texttt{1}\) indicates a cell occupied by a ball, while \(\texttt{0}\), an empty one.) Note that some robots may go from right to left.

Hasan's goal is to have all the balls placed in a row next to each other, i. e. without empty spaces between them. If you have a sequence of robots \(x_1 \rightarrow y_1, ..., x_k \rightarrow y_k\), you can use each robot as many times as you like and in any order to achieve the goal.

You have a sequence of pairs \((x_1, y_1), ..., (x_m, y_m)\). You have to assign a direction to each of them, and you'll get either robot \(x_i \rightarrow y_i\) or \(y_i \rightarrow x_i\) for each pair.

Hasan notices that there is more than one single way to assign the robots. Can you find the number of ways to do it such that his goal is achievable?

Note that the line is infinite in both directions, i.e. there exists cell 0, cell -1, cell -2, etc.

Input

The first line contains two integers \(n\) and \(m\).

The next line contains \(n\) distinct integers \(p_i\) --- the initial locations of all the balls.

The following \(m\) lines contain pairs \((x_i, y_i)\).

• \(1 \le n, m \le 2000\),
• \(1 \le p_i, x_i, y_i \le 10^6\),
• \(x_i \le y_j\).

Output

The number of ways to assign directions modulo \(10^9+7\).

Example

Input:

3 3
1 4 6
3 5
1 4
6 7

Output:

5

Explanation

If we have robot \(1 \rightarrow 4\) its usage allows us to achieve the goal disregarding directions of the other two pairs, i.e. 4 ways to assign directions. Otherwise, having robot \(4 \rightarrow 1\) requires both robots \(5 \rightarrow 3\) and \(7 \rightarrow 6\) to push the balls to cells 0, -1, and -2. Thus, in total there are 5 ways to assign directions.