Giáo sư Thế Vinh dạy toán ở trường đại học. Trong nhóm xeminar có ~N~ sinh viên theo học. Trong bài giảng cuối cùng, giáo sư Thế Vinh 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 khoảng 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. Ví dụ với ~K=3~ có ~3!=6~ hoán vị. Các hoán vị có thể được sắp xếp theo thứ tự từ điển.

Ví dụ với ~K=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~

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, hạng của hoán vị ~(3,1,2)~ là ~5~.

Thế Vinh gán cho mỗi sinh viên của ông ta một hoán vị khác nhau. Tất cả các sinh viên sẽ tính toán hạng của hoán vị mà giáo sư gán cho mình. Thế Vinh sử dụng một thuật toán đơn giản để sinh các hoán vị: Ông ta chọn một hoán vị cơ sở gồm ~K~ số nguyên. Sau đó mỗi sinh viên sẽ nhận được hoán vị của mình bằng cách gửi cho anh (cô) ta một cặp vị trí cần đổi chỗ của hoán vị cơ sở.

Giáo sư Thế Vinh đưa cho Dũng (nhóm trưởng) hoán vị cơ sở và ~N~ cặp vị trí cần đổi chỗ. Hãy viết chương trình giúp Dũng tính hạng các hoán vị của các sinh viên. 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 K \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ở.

Hai số liên tiếp trên dùng một dòng cách nhau bằng khoảng trống (space).

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