首先,中心点是能够直接算出来的
把全部的坐标相加再除n就能够
然后枚举一个不靠近中心的点，枚举它绕中心点旋转的角度。仅仅要枚举50次就能够了
计算出当前枚举的的角度能否形成一个置换群
计算循环节，再用polya定理算个数
#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<cstring>
#include<iomanip>
using namespace std;
#ifdef _WIN32
#define i64 __int64
#define out64 "%I64d\n"
#define in64 "%I64d"
#else
#define i64 long long
#define out64 "%lld\n"
#define in64 "%lld"
#endif
/************ for topcoder by zz1215 *******************/
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define FOR(i,a,b) for( int i = (a) ; i <= (b) ; i ++)
#define FF(i,a) for( int i = 0 ; i < (a) ; i ++)
#define FFD(i,a,b) for( int i = (a) ; i >= (b) ; i --)
#define S64(a) scanf(in64,&a)
#define SS(a) scanf("%d",&a)
#define LL(a) ((a)<<1)
#define RR(a) (((a)<<1)+1)
#define pb push_back
#define pf push_front
#define X first
#define Y second
#define CL(Q) while(!Q.empty())Q.pop()
#define MM(name,what) memset(name,what,sizeof(name))
#define MC(a,b) memcpy(a,b,sizeof(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define read freopen("out.txt","r",stdin)
#define write freopen("out2.txt","w",stdout)
const int inf = 0x3f3f3f3f;
const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL;
const double oo = 10e9;
const double eps = 10e-6;
const double pi = acos(-1.0);
const int maxn = 55;
const int mod = 1000000007;
int n, m, c;
int nx[maxn];
int ny[maxn];
double cita[maxn];
double r[maxn];
double cx, cy;
int a[maxn];
int b[maxn];
int edge[maxn][maxn];
i64 gcd(i64 _a, i64 _b)
{
if (!_a || !_b)
{
return max(_a, _b);
}
i64 _t;
while ((_t = _a % _b))
{
_a = _b;
_b = _t;
}
return _b;
}
i64 ext_gcd(i64 _a, i64 _b, i64 &_x, i64 &_y)
{
if (!_b)
{
_x = 1;
_y = 0;
return _a;
}
i64 _d = ext_gcd(_b, _a % _b, _x, _y);
i64 _t = _x;
_x = _y;
_y = _t - _a / _b * _y;
return _d;
}
i64 invmod(i64 _a, i64 _p)
{
i64 _ans, _y;
ext_gcd(_a, _p, _ans, _y);
_ans < 0 ?_ans += _p : 0; return _ans; } double gao(double x,double y){ if (abs(x) < eps){ if (y>0){ return pi / 2.0; } else{ return pi + pi / 2.0; } } else if (x >= 0 && y >= 0){ return atan(y / x); } else if (x <= 0 && y >= 0){ x = -x; return pi - atan(y / x); } else if (x <= 0 && y <= 0){ x = -x; y = -y; return pi + atan(y / x); } else { y = -y; return 2 * pi - atan(y / x); } } int find(double tcita,double tr){ if (tcita > 2 * pi){ tcita -= 2 * pi; } double tx = cx + tr*cos(tcita); double ty = cy + tr*sin(tcita); for (int i = 1; i <= n; i++){ if (abs(tx - nx[i]) < eps && abs(ty-ny[i]) < eps){ return i; } } return -1; } bool isint(double temp){ int t2 = temp; temp -= t2; if (temp < eps) { return true; } else{ return false; } } bool can(){ int now, to; for (int x = 1; x <= n; x++){ for (int y = 1; y <= n; y++){ now = b[x]; to = b[y]; if (edge[x][y] != edge[now][to]){ return false; } } } return true; } bool vis[maxn]; int count(){ MM(vis, 0); int re = 0; int now, to; for (int x = 1; x <= n; x++){ if (!vis[x]){ now = x; vis[now] = true; re++; while (true){ to = b[now]; if (vis[to]){ break; } else{ vis[to] = true; now = to; } } } } return re; } i64 pow_mod(int x,int temp){ i64 re = 1; for (int i = 1; i <= temp; i++){ re *= x; re %= mod; } return re; } i64 start(){ cx = 0.0; cy = 0.0; for (int i = 1; i <= n; i++){ cx += nx[i]; cy += ny[i]; } cx /= n; cy /= n; double tx, ty; for (int i = 1; i <= n; i++){ tx = nx[i] - cx; ty = ny[i] - cy; r[i] = sqrt(tx*tx + ty*ty); cita[i] = gao(tx, ty); } double spin; i64 ans = 0; i64 sg =0; int id; for (int i = 1; i <= n; i++){ if (abs(cx - nx[i]) > eps || abs(cy - ny[i]) > eps){ id = i; break; } } for (int i = 1; i <= n; i++){ spin = cita[i] - cita[id]; if (abs(r[i] - r[id]) < eps){ bool no = false; for (int x = 1; x <= n; x++){ a[x] = find(cita[x] + spin, r[x]); if (a[x] == -1){ no = true; break; } b[a[x]] = x; } if (no) continue; if (can()){ sg++; ans += pow_mod(c, count()); ans %= mod; } } } ans *= invmod(sg, mod); ans %= mod; return ans; } int main(){ int T; cin >> T; while (T--){ cin >> n >> m >> c; for (int i = 1; i <= n; i++){ cin >> nx[i] >> ny[i]; } for (int i = 0; i <= n; i++){ for (int j = 0; j <= n; j++){ edge[i][j] = 0; } } int now, to; for (int i = 1; i <= m; i++){ cin >> now >> to; edge[now][to] = edge[to][now] = 1; } if (n == 1){ cout << c << endl; continue; } i64 ans = start(); cout << ans << endl; } return 0; }