You are given a permutation of first N natural numbers on which you are to perform K operations of following type: given integers A and B, your task is to swap elements on positions A and B in permutation and then output permutation rank modulo 1000 000 007.

Note: Difference from original task is that elements remain swapped after query.

Input

On first line of standard input you are given two integers (2 ≤ N ≤ 50 000, 1 ≤ K ≤ 30 000), length of permutation and number of operations.
On the next line there is permutation of first N natural numbers.
In next K lines there are two integers A, B ( 1 ≤ A, B ≤ N ).

Output

Output permutation rank after applying each of K operations.

Example

Input:
5 3
1 5 4 2 3
1 3
2 3
2 5

Output:
91
77
90