#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#define MOD 1000000007
#define ll long long
#define N 500001

using namespace std;

map<int,int> val;
int n,m,V,lst,l,r,X[N],Y[N],p[N],q[N],A[N],B[N],tot,flag;
ll ans,sum;

ll qp( ll a , ll b )
{
	ll c = 1;
	while( b )
	{
		if( b & 1 ) c = c * a % MOD;
		b >>= 1;
		a = a * a % MOD;
	}
	return c;
}

struct T
{
	int x,y;
}d[N];

bool cmp( T x , T y )
{
	return x.x < y.x;
}

bool ck( void )
{
	for( int i = 1 ; i <= n ; i ++ )
	{
		if( i < n )
		{
			if( A[i] == q[i] )
			{
				if( B[i] != q[i + 1] )
					return false;
			}
		}
		if( p[i] == 0 ) continue;
		if( q[i] != p[i] )
			return false;
	}
	return true;
}

void dfs2( int k )
{
	if( flag ) return;
	if( k == n + 1 )
	{
		if( ck() ) flag = 1;
		return;
	}
	if( p[k] )
	{
		q[k] = p[k];
		dfs2( k + 1 );
	}
	else
	{
		for( int i = 1 ; i <= V ; i ++ )
			q[k] = i,dfs2( k + 1 ); 
	}
}

void dfs1( int k )
{
	if( k == n )
	{
		flag = 0;
		for( int i = 1 ; i <= n ; i ++ )
			q[i] = p[i];
		dfs2( 1 );
		ans += flag;
		return;	
	}
	for( int i = 1 ; i <= V ; i ++ )
	{
		A[k] = i;
		for( int j = 1 ; j <= V ; j ++ )
			B[k] = j,dfs1( k + 1 );		
	}
	return;
}

int main()
{
	ios::sync_with_stdio( false );
	cin.tie( 0 );
	cout.tie( 0 );
	freopen( "assign.in" , "r" , stdin );
	freopen( "assign.out" , "w" , stdout );
	int T,xx,yy;
	cin >> T;
	while( T -- )
	{
		cin >> n >> m >> V;
		val.clear();
		flag = 0;
		tot = 0;
		for( int i = 1 ; i <= m ; i ++ )
		{
			cin >> xx >> yy; 
			if( !val[xx] )
				val[xx] = yy,tot ++,d[tot].x = xx,d[tot].y = yy;
			if( val[xx] != yy )
				flag = 1;
		}
		ans = 0;
		if( flag )
		{
			cout << 0 << '\n';
			continue;
		}
		m = tot;
		sort( d + 1 , d + m + 1 , cmp );
		if( m == 1 || m == n )
		{
			ans = 1;
			l = r = 1;
			sum = 0;
			for( int i = 2 ; i <= m ; i ++ )
			{
				if( d[i].x - d[i - 1].x == 1 )
					r = i;
				else
				{
					sum += r - l;
					l = r = i;
				}
			}
			sum += r - l;
//			cout << sum << endl;
			ans = qp( ( V - 1 ) * V + 1 , sum ) * qp( V , ( n - 1 - sum ) * 2 ) % MOD;
			cout << ans << '\n';
//			cout << qp( V , n * 2 - 2 ) << '\n';//m = 1
//			cout << qp( ( V - 1 ) * V + 1 , n - 1 ) << '\n';//A
			continue;
		}
		else
		{
			for( int i = 1 ; i <= n + 1 ; i ++ )
				p[i] = q[i] = 0;
			for( int i = 1 ; i <= m ; i ++ )
				p[d[i].x] = d[i].y;
			dfs1( 1 );
			cout << ans << '\n';
		}
	}
	return 0;
}
