순열의 순서

지승이는 대학에서 수학을 가르치고 있다. 이번 학기에는 이산 수학과 조합론을 강의하며, 수강생은 모두 N명이다. 지난 시간에 다룬 내용은 순열의 순서이다.

1부터 K까지의 정수로 이루어진 수열에서 각 정수가 정확히 한 번씩 등장하면 그 수열을 순열이라고 한다. 가능한 순열은 모두 K!개이다. 순열은 앞에서부터 차례대로 값을 비교하는 사전식 순서로 정렬한다. 예를 들어 1, 2, 3으로 만들 수 있는 순열의 순서는 다음과 같다.

1. (1, 2, 3)
2. (1, 3, 2)
3. (2, 1, 3)
4. (2, 3, 1)
5. (3, 1, 2)
6. (3, 2, 1)

모든 순열을 이 순서로 나열했을 때의 1부터 시작하는 번호를 그 순열의 순서라고 한다. 예를 들어 (3, 1, 2)의 순서는 5이다.

지승이는 학생들에게 순열의 순서를 계산하는 숙제를 내려고 한다. 먼저 길이가 K인 순열 하나를 고른다. 이후 각 학생마다 두 위치 A와 B를 정하고, 처음 고른 순열에서 A번째 수와 B번째 수만 서로 바꾼 순열을 그 학생에게 준다. 각 학생의 교환은 서로 독립적이며, 한 학생의 결과가 다른 학생의 순열에 영향을 주지 않는다.

처음 고른 순열과 각 학생에게 주어진 A, B가 주어질 때, 각 교환 뒤 순열의 순서를 구하시오. 값이 매우 커질 수 있으므로 순서를 1,000,000,007로 나눈 나머지를 출력한다.

첫째 줄에 K와 N이 주어진다. K는 순열의 길이, N은 학생의 수이다.

둘째 줄에는 지승이가 처음 고른 순열이 주어진다. 순열은 1부터 K까지의 정수 K개로 이루어져 있으며, 각 정수는 한 번씩만 등장한다.

다음 N개 줄에는 각 학생에게 주어진 두 위치 A와 B가 주어진다.

제한은 다음과 같다.

• 2 ≤ K ≤ 300,000
• 1 ≤ N ≤ 100,000
• 1 ≤ A < B ≤ K

각 질의마다, A번째 수와 B번째 수를 서로 바꾼 순열의 순서를 1,000,000,007로 나눈 나머지를 한 줄에 하나씩 출력한다.