Ngày nay, lĩnh vực an ninh mạng đang dần trở thành một lĩnh vực thiết yếu trong việc bảo mật an toàn thông tin trên toàn thế giới. Tuấn là một kỹ sư an ninh mạng và rất đam mê khám phá các bài toán về mã hóa bảo mật. Cậu đang quan tâm đến bài toán mã hóa một dãy số ~S=(S_1, S_2, \ldots, S_N)~ với các phần tử là số nguyên dương không quá ~K~. Cậu thử nghiệm việc mã hóa bằng cách viết ra tất cả các dãy hậu tố của dãy ~S~. Cụ thể, với mỗi ~i \in \{1, 2, \ldots, N\}~, Tuấn viết ra dãy ~A_i = (S_i, S_{i+1},\ldots,S_N)~. Sau đó, cậu sắp xếp các dãy này tăng dần theo thứ tự từ điển. Cuối cùng, cậu ghi lại độ dày của các dãy theo thứ tự đã sắp xếp, thu được dãy ~L=(L_1, L_2, \ldots, L_N)~ và gọi đây là dãy đặc trưng của ~S~.

Ví dụ, với dãy ~S~ = ~(2, 1, 4, 3, 1, 3, 4)~ thì Tuấn sẽ viết ra ~7~ dãy: ~A_1 = (2, 1, 4, 3, 1, 3, 4)~; ~A_2=(1, 4, 3, 1, 3, 4)~; ~A_3=(4, 3, 1, 3, 4)~; ~A_4=(3, 1, 3, 4)~; ~A_5=(1, 3, 4)~; ~A_6=(3, 4)~; ~A_7=(4)~. Sau khi sắp xếp tăng dần theo thứ tự từ điển, Tuấn thu được: ~(A_5, A_2, A_1, A_4, A_6, A_7, A_3)~. Cuối cùng, Tuấn ghi lại độ dài các dãy theo thứ tự đó và thu được các dãy đặc trưng của ~S~ là ~L =~ (~3, 6, 7, 4, 2, 1, 5~).

Nhắc lại, dãy ~(X_1, X_2, \ldots, X_u)~ được gọi là đi trước dãy ~(Y_1, Y_2, \ldots, Y_v)~ theo thứ tự từ điển nếu một trong hai điều kiện sau thỏa mãn:

• Tồn tại ~i \in \{1, 2, \ldots, min(u, v)\}~ sao cho ~X_1 = Y_1, X_2 = Y_2, \ldots, X_{i - 1} = Y_{i - 1}~ và ~X_i < Y_i~;

• ~X_1 = Y_1, X_2 = Y_2, \ldots, X_u = Y_u~ và ~u < v~.

Bây giờ Tuấn muốn biết khả năng giải mã ngược lại ra dãy ~S~ nếu chỉ biết số ~K,~ dãy ~L~ và phương pháp xây dựng dãy ~L~. Tuấn nhận ra rằng có thể tồn tại nhiều dãy ~S~ có các phần tử là các số nguyên dương không quá ~K~ mà sau khi thực hiện phương pháp mã hóa như trên có thể cho ra cùng một dãy đặc trưng ~L~.

Tiếp tục quá trình thử nghiệm, Tuấn thực hiện ~Q~ phép biến đổi liên tiếp trên dãy ~L~. Với mỗi phép biến đổi, cậu sẽ chọn hai phần tử của dãy ~L~ hiện tại và đổi giá trị cho nhau, sau đó đếm số dãy ~S~ thỏa mãn dãy đặc trưng ~L~ vừa được biến đổi. Sau mỗi phép biến đổi, dãy ~L~ được cập nhật.

Yêu cầu: Cho biết ~N, K~, dãy ~L~ và các phép biến đổi của Tuấn. Trước lần biến đổi đầu tiên và sau mỗi lần biến đổi của Tuấn trên dãy ~L~, hãy tính số lượng dãy ~S~ có ~N~ phần tử, các phần tử là các số nguyên dương không quá ~K~, sao cho dãy đặc trưng của ~S~ là dãy ~L~.

Input

Vào từ file văn bản ENCODE.INP:

• Dòng đầu tiên chứa ba số nguyên ~N, K, Q~ (~1 \leq N, K \leq 5 \times 10^5~, ~0 \leq Q \leq 5 \times 10^5~).

• Dòng thứ hai chứa ~N~ số nguyên dương ~L_1, L_2, \ldots, L_N~. Dữ liệu đảm bảo dãy ~L=(L_1, L_2, \ldots, L_N)~ là một hoán vị của ~N~ số tự nhiên ~1, 2, \ldots, N~.

• Mỗi dòng trong số ~Q~ dòng tiếp theo chứa hai số nguyên dương khác nhau ~i, j~ ~(1 \leq i, j \leq N)~ mô tả một phép biến đổi của Tuấn với ý nghĩa là đổi giá trị của ~L_i~ và ~L_j~ cho nhau.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

In ra file văn bản ENCODE.OUT:

• Gồm ~Q + 1~ dòng, mỗi dòng là phần dư trong phép chia cho ~1\,000\,000\,007~ của số lượng dãy ~S~ tính được cho dãy ~L~ ban đầu và cho dãy ~L~ sau mỗi phép biến đổi theo thứ tự đầu vào.

Scoring

Sample Input 1

3 3 2
3 1 2
2 3
1 2

Sample Output 1

4
4
1

Notes

• Các dãy ~S~ có dãy đặc trưng ~L=(3, 1, 2)~ là: ~(1, 2, 2)~; ~(1, 3, 3)~;, ~(2, 3, 3)~; ~(1, 3, 2)~.

• Các dãy ~S~ có dãy đặc trưng ~L=(3, 2, 1)~ là: ~(1, 1, 2)~; ~(1, 1, 3)~; ~(2, 2, 3)~; ~(1, 2, 3)~.

• Các dãy ~S~ có dãy đặc trưng ~L=(2, 3, 1)~ là: ~(2, 1, 3)~.