#P4228. Tibbar的后花园
Tibbar的后花园
题目描述
在 个互不相同的标号点之间选择一些无向边,得到一张简单无向图。任意两个点至多连一条边,一个点不能和自身连边。
两点的距离是连接它们的最短路包含的边数。三个不同的点在同一个连通分量内,且它们之间的三对距离全部相等时,称它们为一组违规三点。跨连通分量的点对不可达,不能构成违规三点。
求没有违规三点的连边方案数。
输入格式
输入一个整数 ()。
输出格式
输出一个整数,表示方案数对 取模后的值。
样例
3
7
三个标号点之间的三条可能边共有八种选法。只有三角形包含一组两两距离均为 的点,因此有七种合法方案。