忍者查内克先生有一天接到一项任务,去处理正在攻击某个地点的疯蛇。现在,查内克先生已经到达了山丘,而目的地就在这些山丘的正下方。任务区域可以划分为 $$$1000 \times 1000$$$ 方格大小的网格。站点上有 $$$N$$$ 条疯蛇,第 i 条疯蛇位于 $$$(X_i, Y_i)$$$ 广场,危险级别为 $$$B_i$$$。
查内克先生将使用他从第七大人那里学到的影分身之术和螺旋丸来完成这个任务。他的攻击策略如下:
1. Chanek 先生将制作 $$$M$$$ 克隆体。
2.每个分身都会选择一条疯蛇作为攻击目标。每个克隆必须选择不同的疯蛇来攻击。
3. 所有克隆人从山上跳下来,用半径为 $$$R$$$ 的螺旋丸攻击各自选择的目标。如果 $$$(X, Y)$$$ 方格的疯蛇受到直接螺旋丸的攻击,则它和 $$$(X', Y')$$$ 方格中的所有疯蛇都会死亡,其中 $$$max(|X' - X|, |Y' - Y|) \le R$$$ 将会死亡。
4. 真正的Chanek先生将计算本次攻击的得分。分数定义为所有被杀死的蛇的危险级别总和的平方。
现在 Chanek 先生很好奇,每种可能的攻击策略的分数总和是多少?因为这个数字可能很大,所以 Chanek 先生只需要输出模 $$$10^9 + 7$$$。
输入
第一行包含三个整数 $$$N$$$ $$$M$$$ $$$R$$$ $$$(1 \le M \le N \le 2 \cdot 10^3, 0 \le R < 10^3)$$$、疯蛇数量、克隆数量和螺旋丸半径。
接下来的 $$$N$$$ 行每行包含三个整数,$$$X_i$$$、$$$Y_i$$$、dan $$$B_i$$$ $$$(1 \le X_i, Y_i \le 10^3, 1 \le B_i \le 10^6)$$$。保证没有两条疯蛇占据同一个方格。
输出
一行带有一个整数,表示每种可能的攻击策略的分数总和。
示例
输入 #1
4 2 1 1 1 10 2 2 20 2 3 30 5 2 40
输出 #1
33800
注意
这是所有六种可能的攻击策略的说明。圆圈表示选定的疯蛇,蓝色方块表示螺旋丸的区域:
因此,所有攻击的总得分为:$$$3.600 + 3.600 + 4.900 + 3.600 + 10.000 + 8.100 = 33.800$$$。