Cho một hoán vị của dãy ~n~ phần tử ~a_1~, ~a_2~, ..., ~a_n~ gọi là hoán vị gốc và một số các truy vấn hoán vị.

Một truy vấn hoán vị là một cặp (~i~, ~j~) (~1~ ~\leq~ ~i~ ~\leq~ ~j~ ~\leq~ ~n~). Với mỗi truy vấn hoán vị (~i~, ~j~), bạn đổi chỗ ~2~ phần tử tại vị trí ~i~ và vị trí ~j~ và in ra số hiệu hoán vị của dãy hoán vị mới đó. Các truy vấn không ảnh hưởng đến hoán vị gốc.

Ví dụ, nếu hoán vị gốc là (~1~, ~5~, ~4~, ~2~, ~3~) và các cặp là (~1~, ~3~), (~2~, ~3~) và (~2~, ~5~) thì ta sẽ thu được ~3~ hoán vị là: (~4~, ~5~, ~1~, ~2~, ~3~), (~1~, ~4~, ~5~, ~2~, ~3~) và (~1~, ~3~, ~4~, ~2~, ~5~). Chúng có các số hiệu là ~91~, ~17~ và ~9~.

Yêu cầu

In ra số hiệu của các hoán vị. Các số này có thể rất lớn nên đưa ra sau khi đã mod ~10^9 + 7~.

Input

• Dòng ~1~: ~n~ (~1~ ~\leq~ ~n~ ~\leq~ ~3 \times 10^5~) và ~q~ (~1~ ~\leq~ ~q~ ~\leq~ ~10^5~) số lượng truy vấn hoán vị.
• Dòng ~2~: ~n~ số ~a_1~, ~a_2~, ..., ~a_n~.
• Trong ~q~ dòng sau, mỗi dòng chứa ~2~ số ~i~, ~j~ biểu thị một truy vấn hoán vị (~1~ ~\leq~ ~i~ ~\leq~ ~j~ ~\leq~ ~n~).

Output

In ra ~q~ số nguyên, mỗi số ~1~ dòng là số hiệu của mỗi hoán vị mod ~10^9 + 7~ theo thứ tự xuất hiện trong input.

Sample Input

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

Sample Output

91
17
9