https://drive.google.com/file/d/1jsXcDAapaGqI1NcEfL19_o-uVwKwQR9K/view?usp=sharing

Sau một cuộc phiêu lưu đầy kịch tính qua 8 vòng loại đầy thách thức, Huy đã đặt bước chân tới rương kho báu huyền bí mà anh ta luôn ao ước. Nhưng để mở khóa kho báu này, Huy đối diện với một thách thức cuối cùng - giải mã mật khẩu kỳ lạ.

Trên chiếc khóa đặc biệt này, Huy phát hiện có hai dãy ô nằm ngang có cùng độ dài, mỗi ô chứa một con số. Đặc biệt, dãy ở phía dưới có thể xoay như một vòng tròn, tức là sau mỗi lần xoay, mỗi con số sẽ di chuyển sang trái một ô, và ô đầu tiên sẽ trở thành ô cuối cùng.

Huy quyết định thử tính tổng của tích từng cặp số tương ứng giữa hai dãy ô, ghi chép lại kết quả, xoay dãy ở phía dưới và lặp lại quá trình này. Một lúc sau, Huy rút ra dự đoán rằng mật khẩu cần tìm là tổng của \(k\) số đầu tiên theo ghi chép của mình.

Tuy nhiên, vì \(k\) quá lớn nên Huy khó có thể tự tìm ra mật khẩu. Anh ta hy vọng bạn có thể giúp anh ta vượt qua thách thức này và giành được rương kho báu mơ ước.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) \((1 \leq n \leq 10^5, 1 \leq k \leq 10^9)\) lần lượt là số lượng ô của cả hai dãy và số lượng số cần tính toán.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^9)\) là những số được ghi trong mỗi ô của dãy phía trên.
• Dòng tiếp theo chứa \(n\) số nguyên \(b_1, b_2, \ldots, b_n\) \((1 \leq b_i \leq 10^9)\) là những số được ghi trong mỗi ô của dãy phía dưới.

Output

• Một số nguyên duy nhất là mật khẩu mà bạn tìm được. Vì số có thể rất lớn nên bạn chỉ cần in phần dư của nó khi chia cho \(10^9 + 7\).

Ví dụ

Input

5 3
1 2 3 4 5
6 7 8 9 10

Output

365

Giải thích

Ràng buộc

• Subtask \(1\) (\(28\%\) số điểm): \(n, k \leq 10^3\).
• Subtask \(2\) (\(33\%\) số điểm): \(n \leq 10^3\).
• Subtask \(3\) (\(39\%\) số điểm): Không có ràng buộc gì thêm.