#P18339. Gold Miner
Gold Miner
Gold Miner
标准输入,标准输出。
Putata 最近迷上了黄金矿工。游戏在一个二维平面上进行,地图中有 块金子,第 块位于 ,其中 。
玩家位于地面上的 。每关的目标是收集 块金子。由于特殊的地质条件,当玩家与一块金子的欧氏距离为 时,拉动它所需的力为 ;收集这块金子消耗的能量,等于将它拉到玩家所在位置所需的功。
对于随距离变化的力,功应沿位移积分。因此,收集距离为 的一块金子所需的功是
Putata 会采取最优策略,在通过关卡的前提下,使总能量消耗最小。
现在 Budada 设计了 个随机关卡。对于第 个关卡,玩家的位置 是从实数区间 中独立、均匀随机产生的,需要收集的金子数为 。请计算每个关卡中,最小总能量消耗的期望,对 取模。
位置确定后才能选择收集哪些金子;这个最优选择可以随位置 改变。若 ,玩家的位置就是这个确定的点。
答案可以表示为最简分数 ,题目保证 。请输出唯一整数 ,满足
输入格式
第一行包含两个整数 ,分别表示金块数和关卡数。
接下来 行,每行包含两个整数 ,表示第 块金子的位置。
接下来 行,每行包含三个整数 ,描述一个随机关卡。
不同金块可以位于同一个坐标,仍然分别计数。第二个样例中就存在这样的金块。
输出格式
输出 行。第 行包含一个整数,表示第 个关卡的答案。
本题输出模数意义下的整数,不输出实数近似值。
数据范围
- ;
- ;
- ;
- ;
- ;
- 。
本题只有一组数据,没有测试用例数。
样例输入 1
4 4
1 -2
4 -1
4 -3
5 -2
2 3 1
0 6 4
3 4 2
4 7 2
样例输出 1
333333339
40
666666679
9
样例输入 2
6 10
7 -5
2 -7
2 -7
5 -3
9 -4
5 -3
2 4 1
2 10 2
5 8 3
3 9 1
5 8 5
1 2 4
4 5 3
7 10 6
3 8 3
2 9 2
样例输出 2
333333349
846354201
625000051
406250015
143
333333477
50
273
575000054
443452410
样例说明
第一个样例的四个期望分别为