Mối nguy từ đàn rắn dữ

Khu vực nhiệm vụ là một lưới ô vuông kích thước $1000\times 1000$. Trên lưới có $N$ con rắn; con rắn thứ $i$ nằm tại ô $(X_i,Y_i)$ và có mức độ nguy hiểm $B_i$. Không có hai con rắn nào ở cùng một ô.

Ta sẽ tạo ra $M$ phân thân để tấn công. Mỗi phân thân chọn tấn công một con rắn làm mục tiêu, và các phân thân phải chọn các con rắn khác nhau (mỗi con rắn được chọn làm mục tiêu bởi nhiều nhất một phân thân). Tất cả phân thân tấn công đồng thời bằng đòn tấn công có bán kính $R$: khi con rắn ở ô $(X,Y)$ bị chọn làm mục tiêu, thì nó cùng mọi con rắn ở ô $(X^{\prime },Y^{\prime })$ thỏa mãn $max(|X^{\prime }-X|,|Y^{\prime }-Y|)\le R$ đều bị tiêu diệt.

Với mỗi cách chọn ra $M$ con rắn làm mục tiêu, điểm của cách đó được định nghĩa là bình phương của tổng mức độ nguy hiểm của tất cả các con rắn bị tiêu diệt.

Hãy tính tổng điểm trên tất cả các cách chọn $M$ con rắn làm mục tiêu (có $\left(\genfrac{}{}{0ex}{}{N}{M}\right)$ cách). Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $N$, $M$, $R$.
• $N$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $X_i$, $Y_i$, $B_i$.

Dữ liệu ra

• In ra một số nguyên duy nhất là tổng điểm trên tất cả các cách chọn, lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le M\le N\le 2000$
• $0\le R<1000$
• $1\le X_i,Y_i\le 1000$
• $1\le B_i\le {10}^6$
• Không có hai con rắn nào ở cùng một ô.

Ví dụ