Có ~n~ ngày với chỉ số thị trường ~a_1,a_2,\ldots,a_n~. Cần chọn đúng ~k~ ngày theo thứ tự tăng dần chỉ số, ngày được chọn thứ ~j~ nhận trọng số ~w_j~.

Yêu cầu

Tìm tổng lợi nhuận lớn nhất ~\sum_{j=1}^{k} w_j \cdot a_{i_j}~ và số cách chọn đạt lợi nhuận lớn nhất đó, lấy dư modulo ~10^9+7~.

Input

Dòng đầu chứa hai số ~n,k~ ~(1 \le k \le n \le 10^5, k \le 100)~.

Dòng thứ hai chứa ~n~ số ~a_i~ ~(1 \le a_i \le 10^9)~.

Dòng thứ ba chứa ~k~ số ~w_j~ ~(1 \le w_j \le 10^6)~.

Output

Dòng đầu in lợi nhuận lớn nhất.

Dòng thứ hai in số cách chọn đạt được lợi nhuận đó modulo ~10^9+7~.

Subtask

• Subtask 1: ~n \le 10^2~, ~k=1~.
• Subtask 2,3: ~n \le 10^5~, ~k \le 100~.

Ví dụ

3 2
1 2 3
3 2

10
1