Một hội thi có ~n~ thí sinh tham gia, các thí sinh đến từ ~m~ đoàn. Thí sinh thứ ~i (i=1, 2,..., n)~ thuộc đoàn ~t_i (1 \le t_i \le m)~ và có mức độ vui vẻ là số nguyên dương ~h_i (1 \le h_i \le 10^6)~. Trong buổi liên hoan, mỗi thí sinh sẽ đều đi bắt tay chào hỏi tất cả các thí sinh của các đoàn khác. Khi đó, nếu thí sinh thứ ~i~ bắt tay với thí sinh thứ ~j~ (thí sinh ~i~ và ~j~ không cùng đoàn) sẽ tạo ra độ "Hạnh phúc" là ~h_i \times h_j~. Ban tổ chức muốn tính tổng độ "Hạnh phúc" sau khi các thí sinh đều đã bắt tay nhau.
Yêu cầu: Cho ~n~ cặp số nguyên dương, cặp số ~(t_i, h_i)~ tương ứng là thông tin về đoàn và mức độ vui vẻ của thí sinh thứ ~i (1 \le i \le n)~. Gọi ~p~ là tổng độ "Hạnh phúc" sau khi các thí sinh đều đã bắt tay nhau, hãy tính ~p \% (10^9+7)~, trong đó phép toán ~\%~ là chia lấy dư.
Dữ liệu:
- Dòng đầu tiên chứa hai số nguyên dương ~n, m (m \le n)~;
- Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa hai số nguyên dương ~t_i, h_i~.
Kết quả:
- Ghi ra một số nguyên là phần dư trong phép chia ~p~ cho ~10^9+7~.
Ràng buộc:
- Có ~40\%~ số test ứng với ~40\%~ số điểm của bài có ~m \le 1000; n \le 1000~;
- Có ~30\%~ số test khác ứng với ~30\%~ số điểm của bài có ~m \le 1000; n \le 10^5~;
- Có ~30\%~ số test còn lại ứng với ~30\%~ số điểm của bài có có ~n \le 10^5~.
Ví dụ:
Sample Input
3 2
1 10
2 30
1 20
Sample Output
900
Comments