ASISTENT  Asistent
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
hide comments
Scape:
20160308 23:03:13
Time limit is indeed too strict. O(N log^2 N) times out... 

applepi:
20110915 02:07:18
Time Limit may be too strict T_T 

Vladimir Kirichenkoff:
20100730 22:53:02
it's a number of the permutation. For example, rank 123  1, rank 132  2, rank 213  3, rank 231  4, rank 312  5, rank 321 = 6. 

Ivan Katanic:
20101107 13:53:53
Yes, but you probably have big constant factor. Your solution times out on 6th case and it would fail even if time limit is 10 s, so far accepted solutions passed even 10th test under 67 s. 

Lox:
20100627 11:47:05
Is an O(NlogN+K(logN)^2) approach expected to be accepted? I've got TLE. :S

Added by:  Ivan Katanic 
Date:  20100623 
Time limit:  1.585s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  Modified task from Croatian IOI Team Selection Test 