Dũng luôn có một phong cách rất đặc biệt trong cách lập trình cũng như cách anh ấy mã hóa dữ liệu. Đây là một cách mã hóa dữ liệu rất dị mà Dũng đã thiết kế:

• Đầu tiên, chương trình sẽ xây dựng một dãy \(a\) gồm \(n\) số nguyên;
• Tiếp theo, chương trình sẽ xây dựng một tập hợp gồm tất cả các dãy con phân biệt khác rỗng của \(a\) và được sắp xếp tăng dần theo thứ tự từ điển;
• Sau đó, chương trình sẽ chọn một số nguyên \(k\) bất kỳ rồi bắt đầu thực hiện mã hóa theo số nguyên này;
• Cuối cùng, chương trình sẽ đưa ra dãy \(a\) và dãy thứ \(k\) trong tập hợp.

Nhắc lại, dãy con của một dãy được tạo thành bằng cách xóa đi một số phần tử và giữ nguyên thứ tự của các phần tử còn lại. Và dãy \(x\) có thứ tự từ điển nhỏ hơn dãy \(y\) nếu \(x\) là một tiền tố của \(y\) (và \(x \neq y\)) hoặc tồn tại một vị trí \(i\) (\(1 \leq i \leq \min(|x|, |y|)\)) mà với mọi \(j\) (\(1 \leq j < i\)) \(x_j = y_j\) và \(x_i < y_i\).

Để giải mã, người dùng cần nhập vào số nguyên \(k\) mà chương trình đã chọn để mã hóa.

Sau khi thử nghiệm, Dũng nhận được hai dãy nhưng lại không biết cách nào để tìm lại số nguyên \(k\) nên đã đã nhờ đến bạn. Với kinh nghiệm của bản thân, hãy giúp Dũng tìm lại nhé.

Ngoài ra, dãy thứ \(k\) mà chương trình đưa ra có thể là không phải là dãy con của \(a\) do chương trình bị lỗi (Có thể do \(k\) âm chăng?).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(1 \leq m \leq n \leq 5 \times 10^5\)) lần lượt là độ dài của dãy \(a\) và dãy thứ \(k\) trong tập hợp.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq n\)) mô tả dãy \(a\).
• Dòng tiếp theo chứa \(m\) số nguyên \(b_1, b_2, \ldots, b_m\) (\(1 \leq b_i \leq n\)) mô tả dãy thứ \(k\) trong tập hợp.

Output

• Trong trường hợp chương trình bị lỗi, hãy in \(-1\). Ngược lại, in ra \(k\) là số nguyên mà chương trinh đã chọn. Vì \(k\) có thể rất lớn nên bạn chỉ cần in phần dư của \(k\) khi chia cho \(10^9 + 7\), còn lại để Dũng tự lo.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 15\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 5 \times 10^3\) và tất cả số nguyên trong dãy \(a\) đôi một phân biệt.
• Subtask \(3\) (\(15\%\) số điểm): Tất cả số nguyên trong dãy \(a\) đôi một phân biệt.
• Subtask \(4\) (\(25\%\) số điểm): \(n \leq 5 \times 10^3\).
• Subtask \(5\) (\(15\%\) số điểm): không có ràng buộc gì thêm.

Example

4 2
3 1 3 1
3 1

6

4 2
3 1 3 1
3 2

-1