该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

What is wind?

When I was a child, my mother told me that wind is the graceful dance of fairies.

In elementary school, textbooks told me that wind arises when cold and warm regions meet.

In high school, geography lessons explained that wind originates from atmospheric circulation near the ground and at high altitudes, caused by pressure differences due to temperature variations.

But I know that all three explanations are correct.

When you dance for me, when a cold heart meets that warmth, when I encounter you:

I think I have seen the wind.

Problem Description

There is a splendid and vast sea of flowers, divided by gardeners into ( n ) flower beds, numbered from ( 1 ) to ( n ). Initially, the ( i )-th flower bed is planted with flowers of variety ( a_i ).

( m ) magical flower breezes blow in succession. When the ( i )-th breeze blows, all flowers of variety ( x_i ) change into variety ( y_i ). Note that ( x_i \ne y_i ) is not necessarily true.

After the ( m ) breezes have passed, the sea of flowers has transformed into a sight that Muxue dares not visit again. Now, Muxue asks you to tell him the result of the product of the variety numbers of all flower beds modulo ( 10^9 + 7 ). This number has no elegant properties, but it can prevent all the pain brought by revisiting. He knows that he has used the knowledge of this sea of flowers, encountered in time.

Input Format

The first line contains two integers ( n, m ), separated by a space.

The next line contains ( n ) integers ( a_i ), separated by spaces.

The following ( m ) lines each contain two integers ( x_i, y_i ), as described in the problem.

Output Format

A single integer, representing the product of the variety numbers of all flower beds modulo ( 10^9 + 7 ).

Sample Input 1

3 2
1 2 3
4 2
1 2

Sample Output 1

12

Sample Input 2

5 3
1 2 1 2 3
1 4
5 4
4 3

Sample Output 2

108

Data Constraints

Subtask 1 (30 points): ( n, m = 1 ).

Subtask 2 (20 points): ( x_i = y_i ), ( n, m \leq 1000 ).

Subtask 3 (20 points): ( n, m \leq 1000 ).

Subtask 4 (30 points): No additional constraints.

For all data, ( 1 \leq n, m \leq 10^5 ), ( 1 \leq a_i, x_i, y_i \leq 10^5 ).