Giáo sư Math dạy toán ở trường đại học Uni có ~n~ sinh viên theo học. Trong chuyên đề số học gần đây, giáo sư Math đã nói về hạng của các hoán vị.

Một dãy gồm ~k~ số nguyên có giá trị nằm trong đoạn từ ~1~ đến ~k~ sao cho mỗi số xuất hiện đúng ~1~ lần được gọi là một hoán vị. Dễ dàng nhận thấy có tất cả ~k!~ hoán vị khác nhau. Các hoán vị này được sắp xếp theo thứ tự từ điển.

Ví dụ: với ~k = 3~, ta có ~3! = 6~ hoán vị theo thứ tự từ điển như sau:

1. ~(1,2,3)~

2. ~(1,3,2)~

3. ~(2,1,3)~

4. ~(2,3,1)~

5. ~(3,1,2)~

6. ~(3,2,1)~

Vị trí của hoán vị trong thứ tự từ điển được gọi là hạng của hoán vị. Trong ví dụ trên, hoán vị ~(3,1,2)~ có hạng là ~5~.

Giáo sư Math gán cho mỗi sinh viên của ông ta một hoán vị. Tất cả các sinh viên sẽ tính toán để tìm hạng của hoán vị mà giáo sư gán cho mình. Giáo sư Math sử dụng một thuật toán đơn giản để sinh các hoán vị và chọn một hoán vị cơ sở gồm ~k~ số nguyên. Sau đó, ông gửi cho mỗi sinh viên ~2~ số nguyên ~a,b~ lần lượt là hai vị trí cần đổi chỗ trong hoán vị cơ sở. Sau khi thực hiện hoán đổi hai vị trí trong hoán vị cơ sở, sinh viên sẽ có được hoán vị của mình.

Math đưa ra một hoán vị cơ sở và ~n~ cặp vị trí cần đổi chỗ cho ~n~ sinh viên.

Yêu cầu: Hãy viết chương trình giúp các sinh viên tính hạng hoán vị của mình. Vì kết quả có thể rất lớn nên chỉ cần giữ lại phần dư khi chia cho ~10^9 + 7~.

Input

• Dòng đầu tiên chứa hai số nguyên ~k~ và ~n~ ~(2 \le k \le 3 \cdot 10^5; 1 \le n \le 10^5)~;

• Dòng thứ hai chứa ~k~ số nguyên là hoán vị cơ sở;

• ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a,b~ ~(1 \le a < b \le k)~ thể hiện hai vị trí cần đổi chỗ hoán vị cơ sở.

Output

Gồm ~n~ số nguyên, mỗi số trên một dòng là hạng các hoán vị của các sinh viên theo thứ tự các cặp đổi chỗ trong dữ liệu vào.

Scoring

Sample Input 1

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

Sample Output 1

91
17
9

Notes

Ở ví dụ trên, hoán vị cơ sở được giáo sư cho ban đầu là ~(1,5,4,2,3)~ và có hạng là ~23~. Với các cặp vị trí giáo sư giao cho các sinh viên thì:

• Cặp ~(1,3)~: Hoán vị cơ sở ban đầu trở thành ~(4,5,1,2,3)~ và có hạng là ~91~;

• Cặp ~(2,3)~: Hoán vị cơ sở ban đầu trở thành ~(1,4,5,2,3)~ và có hạng là ~17~;

• Cặp ~(2,5)~: Hoán vị cơ sở ban đầu trở thành ~(1,3,4,2,5)~ và có hạng là ~9~.