Bạn được cho hai mảng có độ dài ~n~ .

• Phần tử thứ ~i~ của mảng thứ nhất là ~a_i~ .
• Phần tử thứ ~i~ của mảng thứ hai là ~b_i~ .

Một cách chia cả hai mảng thành các mảng con không rỗng được gọi là tốt nếu thỏa mãn các điều kiện sau:

• Mỗi phần tử thuộc đúng một mảng con duy nhất.
• Số lượng mảng con của cả hai mảng bằng nhau, tức là nếu mảng thứ nhất được chia thành đúng ~k~ mảng con, thì mảng thứ hai cũng phải được chia thành đúng ~k~ mảng con.
• Với mọi ~1 \leq i \leq k~, trung bình cộng của mảng con thứ ~i~ bên trái mảng thứ nhất phải nhỏ hơn hoặc bằng trung bình cộng của mảng con thứ ~i~ bên trái mảng thứ hai.

Yêu cầu: Tính số cách để chia cả hai mảng thành các mảng con không rỗng thỏa mãn các điều kiện trên. Kết quả phải được chia dư với ~10^9 + 7~. Hai cách được xem là khác nhau nếu số lượng mảng con khác nhau hoặc nếu một phần tử thuộc về mảng con khác nhau.

Dữ liệu vào từ tệp văn bản: TRUNGBINHCONG.INP

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \leq n \leq 500)~.
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \leq a_i \leq 10^6)~.
• DDòng cuối cùng chứa ~N~ số nguyên ~b_1, b_2, \dots, b_n~ ~(1 \leq b_i \leq 10^6)~.

Kết quả ghi ra tệp văn bản: TRUNGBINHCONG.OUT

• In ra số cách chia mảng thỏa mãn các điều kiện, chia dư với ~10^9 + 7~.

Scoring

• Subtask ~1~ (~20\%~ số điểm): ~n \le 10~
• Subtask ~2~ (~30\%~ số điểm): ~n \le 80~
• Subtask ~3~ (~30\%~ số điểm): ~n \le 300~
• Subtask ~4~ (~20\%~ số điểm): Không giới hạn gì thêm.

Example

Sample Input 1

3
1 3 2
2 2 2

Sample Output 1

3

Note

Ba cách hợp lệ là:

• Chia mảng thứ nhất thành ~[1, 3], [2]~ và mảng thứ hai thành ~[2, 2], [2]~.
• Chia mảng thứ nhất thành ~[1, 3], [2]~ và mảng thứ hai thành ~[2], [2, 2]~.
• Chia mảng thứ nhất thành ~[1, 3, 2]~ và mảng thứ hai thành ~[2, 2, 2]~.

Trong một trò chơi, có một robot di chuyển trên một bản đồ dạng cây gồm ~𝑁~ ngọn núi và ~𝑁 − 1~ con đường nối các ngọn núi. Mỗi ngọn núi có ~𝐾~ kho báu và mỗi con đường nối hai ngọn núi đều có ~2~ kho báu. Quy tắc di chuyển của robot như sau:

• Robot chọn một ngọn núi để xuất phát~;~
• Tại mỗi lượt di chuyển qua một ngọn núi hoặc một con đường, robot khai thác để lấy một kho báu và di chuyển tiếp~;~
• Robot có thể di chuyển từ ngọn núi ~𝑢~ đến ~𝑣~ nếu thoả mãn cả hai điều kiện: con đường nối ngọn núi ~u~ đến ngọn núi ~𝑣~ còn lại ít nhất một kho báu và ngọn núi ~𝑣~ còn lại ít nhất một kho báu. Nếu không còn kho báu, ngọn núi và con đường sẽ bị phá huỷ, robot không thể di chuyển đến.

Yêu cầu: Em hãy tính xem robot có thể đi qua nhiều nhất bao nhiêu con đường.

Dữ liệu nhập vào từ file văn bản TKB.INP:

• Dòng đầu tiên chứa hai số nguyên dương ~𝑁, 𝐾~ ~(𝑁 ≤ 10^5; \ 𝐾 ≤ 10^9);~
• ~𝑁 − 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~𝑢, 𝑣~ ~(1 ≤ 𝑢, 𝑣 ≤ 𝑁)~ mô tả con đường nối hai ngọn núi.

Kết quả ghi ra file văn bản TKB.OUT:

In ra một số nguyên là số lượng con đường nhiều nhất mà robot đi qua.

Ràng buộc

• Có ~30\%~ số test ứng với ~30\%~ số điểm của bài thoả mãn: ~𝐾 = 1;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 20;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 300; \ 𝐾 = 2;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 1000;~
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

7 1
1 2
2 3
4 2
5 1
6 1
6 7

Output

4

Giải thích

Robot có thể di chuyển theo thứ tự các ngọn núi: ~3 − 2 − 1 − 6 − 7~. Robot đi qua 4 con đường.

Input

4 3
1 2
2 4
2 3

Output

6

Giải thích

Robot có thể di chuyển theo thứ tự các ngọn núi: ~1 − 2 − 4 − 2 − 3 − 2 − 1~. Robot đi qua ~6~ con đường.

Bảo Bay Bổng được mời về làm việc cho cơ quan hàng không vũ trụ NASAR. Cơ quan này đang thực hiện một dự án khám phá hành tinh XYZ, nơi được cho là xuất hiện sự sống. Vì hành tinh XYZ rất lớn nên cơ quan này mới đi thám hiểm được một phần diện tích hình chữ nhật có kích thước ~m \times n~, với các hàng được đánh số từ ~1~ tới ~m~ và các cột được đánh số từ ~1~ tới ~n~.

Những khu vực ngoài hình chữ nhật này được coi là nguy hiểm và không được phép làm việc tại đó. Trong khu vực ~m \times n~ này, người ta đã chọn ra một số vị trí có toạ độ nguyên để xây dựng ~S~ trạm phát sóng và ~T~ trạm thu sóng phục vụ cho công việc nghiên cứu (ở cùng một toạ độ có thể đặt đồng thời nhiều trạm phát sóng và thu sóng). Vào thời điểm ~0~, các trạm phát sóng sẽ đồng loạt phát ra các nguồn sóng. Nếu ở thời điểm ~t~, sóng đang ở toạ độ ~(i, j)~ thì ở thời điểm ~t + 1~, sóng sẽ lan sang ~4~ ô kề cạnh với nó, cụ thể là ~(i - 1, j)~,~(i, j - 1)~,~(i + 1, j)~,~(i, j + 1)~. Thời điểm để một trạm thu sóng nhận được sóng là thời điểm nhỏ nhất sao cho có sóng từ một trạm phát sóng nào đó lan ra tới toạ độ trạm thu sóng này.

Hiện giờ, thời gian để tất cả các trạm thu sóng đều nhận được sóng là lâu hơn so với kế hoạch của NASAR cho nên họ muốn nhờ Bảo Bay Bổng công việc như sau: Hãy tìm cách đặt thêm một trạm phát sóng nữa sao cho thời gian để toàn bộ ~T~ thiết bị thu sóng đều nhận được sóng là nhỏ nhất có thể. Đồng thời, hãy đếm xem có bao nhiêu vị trí có thể đặt trạm phát sóng mới để đạt được thời gian đó.

Bảo Bay Bổng đã giải quyết hai vấn đề trên nhưng chưa chắc chắn về kết quả của mình. Bảo Bay Bổng muốn nhờ bạn tính toán lại để đối chiếu kết quả. Hãy giúp Bảo Bay Bổng hoàn thành công việc của NASAR giao cho.

Input: Nhập từ file "THUPHATSONG.INP"

• Dòng đầu tiên chứa hai số nguyên dương ~m, n~ ~(1 \le m, n \le 10^5)~.
• Dòng thứ hai chứa hai số nguyên không âm ~S, T~ ~(0 \le S \le 10^5, 1 \le T \le 10^5)~.
• ~S~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x, y~ là toạ độ của các trạm phát sóng ~(1 \le x \le m, 1 \le y \le n)~.
• ~T~ dòng cuối cùng, mỗi dòng chứa hai số nguyên ~x, y~ là toạ độ của các trạm thu sóng ~(1 \le x \le m, 1 \le y \le n)~.

Output: Xuất ra file "THUPHATSONG.OUT"

In ra hai số nguyên cách nhau bởi một dấu cách:

• Số thứ nhất là thời gian nhỏ nhất để tất cả ~T~ trạm thu sóng nhận được sóng sau khi xây thêm trạm phát sóng thứ ~S + 1~.

• Số thứ hai là số lượng vị trí có thể đặt trạm phát sóng thứ ~S + 1~. Các vị trí này phải là các toạ độ nguyên nằm trong phạm vi hinh chữ nhật an toàn ~m \times n~ và giúp cho thời gian để toàn bộ ~T~ trạm thu sóng nhận được sóng là nhỏ nhất có thể.

Ví Dụ

Sample Input 1

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

Sample Output 1

1 4

Sample Input 2

2 3
0 1
1 1

Sample Output 2

0 1

Sample Input 3

2 3
1 1
1 2
1 2

Sample Output 3

0 6

Giải thích

• Hình ảnh minh hoạ cho ví dụ đầu tiên:

  • Các trạm thu sóng kí hiệu lần lượt là ~T_1, T_2, T_3, T_4~.

  • Trạm phát sóng thứ nhất kí hiệu là ~S_1~, phát ra sóng màu xanh lá cây.

  • Trạm phát sóng thứ hai kí hiệu là ~S_2~, phát ra sóng màu xanh da trời.

  • Trạm phát sóng được đặt thêm vào kí hiệu là ~S_3~, phát ra sóng màu vàng.

  • Dưới đây là hình ảnh của các trạm sóng khi chưa đặt thêm trạm phát sóng mới:

    

  • Khi chưa đặt thêm trạm phát sóng mới, các trạm thu sóng ~T_1, T_2, T_4~ nhận được sóng tại thời điểm ~1~. Trong khi đó, trạm ~T_3~ nhận được sóng tại thời điểm ~2~. Do đó, thời gian nhỏ nhất để tất cả các trạm đều nhận được sóng là thời điểm ~2~.

  • Dưới đây là hình ảnh của các cách đặt trạm sóng ~S_3~ để thời gian tất cả các trạm thu sóng nhận được sóng là nhỏ nhất có thể:

  

  • Bây giờ, tất cả các trạm thu sóng đều nhận được sóng tại thời điểm ~1~.

• Ở ví dụ thứ hai, việc đặt trạm phát sóng tại ~(1, 1)~ sẽ giúp cho trạm thu sóng nhận sóng ngay tại thời điểm ~0~.

• Ở ví dụ cuối cùng, bất kể đặt trạm phát sóng mới tại đâu, trạm thu sóng đều bắt được sóng ngay tại thời điểm ~0~ do đã có sẵn một trạm phát sóng đặt trùng toạ độ tại đó.

Giới hạn

• Subtask 1 (10%): ~m, n, S, T \le 50~
• Subtask 2 (20%): ~S = 0; m, n, T \le 500~
• Subtask 3 (30%): ~S = 0~
• Subtask 4 (20%): ~m, n, S, T \le 5000~
• Subtask 5 (20%): Không có ràng buộc gì thêm