参考博客:https://blog.csdn.net/alpc_wt/article/details/47057517
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
const int N=400+10;
const ll mod=10007;
struct point
{
int x,y;
int id;
}p[N];
bool d[N][N],f[N][N];
int T,n,r;
int flag;
ll dis(point a,point b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int online(point a,point b,point c)
{
return (ll)(a.x-c.x)*(b.y-c.y)==(ll)(b.x-c.x)*(a.y-c.y);
}
void build()
{
memset(d,0,sizeof(d));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(i!=j)
{
if(dis(p[i],p[j])<=(ll)r*r)
{
int ok=1;
for(int k=0;k<n;k++)
if(k!=i&&k!=j)
{
if(p[i].x<=p[k].x&&p[k].x<=p[j].x||p[j].x<=p[k].x&&p[k].x<=p[i].x)
{
if(online(p[i],p[j],p[k]))
{
ok=0;
break;
}
}
}
if(ok) d[i][j]=1;
}
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
f[i][j]=d[i][j];
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
f[i][j]=f[i][j]|(f[i][k]&&f[k][j]);
flag=1;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(!f[i][j]) flag=0;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1l;y=0;
return a;
}
ll d=exgcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-a/b*y;
return d;
}
ll gauss(int C[][N],int n)
{
ll ans=1l;
int flag=1;
int i,j,k;
for(int i=0;i<n;i++)
{
if(C[i][i]==0)
{
for(j=i+1;j<n;j++)
if(C[i][j]) break;
if(j==n) return 0;
flag=!flag;
for(int k=i;k<n;k++)
swap(C[i][k],C[j][k]);
}
ans=ans*C[i][i]%mod;
ll x,y;
int tp=exgcd(C[i][i],mod,x,y);
for(k=i+1;k<n;k++)
C[i][k]=C[i][k]*x%mod;
for(int j=i+1;j<n;j++)
for(int k=i+1;k<n;k++)
{
C[j][k]=(C[j][k]-(ll)C[j][i]*C[i][k])%mod;
if(j==k)
C[j][k]=(C[j][k]+mod)%mod;
}
for(k=i+1;k<n;k++)
C[i][k]=(ll)C[i][k]*C[i][i]%mod;
}
ans=(ans%mod+mod)%mod;
if(flag) return ans;
else return mod-ans;
}
int Kir[N][N];
int solve()
{
memset(Kir,0,sizeof(Kir));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
Kir[i][i]+=d[i][j];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
Kir[i][j]-=d[i][j];
return gauss(Kir,n-1);
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&r);
for(int i=0;i<n;i++)
{
scanf("%d%d",&p[i].x,&p[i].y);
p[i].id=i;
}
build();
if(flag==0)
{
printf("-1\n");
continue;
}
ll ans=solve();
printf("%lld\n",ans);
}
return 0;
}