#P18077. All-Star Showdown
All-Star Showdown
All-Star Showdown
有 个点。第 个点的三维坐标为 ,权值为 。
将每个点恰好分到红队或蓝队。一个划分合法,当且仅当任意两个属于同一队的不同点,其欧氏距离都不小于 。
红队的价值是红队所有点的权值之积。对每个 ,求所有红队恰有 个点的合法划分中,红队价值的总和,对 取模。
输入格式
本题只有一组数据。
第一行两个整数 。
接下来 行,每行四个整数 。
输出格式
输出 行,第 行为红队大小恰为 时的答案。
数据范围
- ;
- ;
- 。
不同点的坐标可以相同;距离恰好等于 时允许同队。
样例 1
输入:
3 1
1 1 1 1
1 2 1 10
1 2 3 100
输出:
111
1110
样例 2
输入:
3 2
1 1 1 1
1 2 1 10
1 2 3 100
输出:
11
1100
样例 3
输入:
3 2
2 1 1 1
1 2 1 10
1 1 2 100
输出:
0
0