#include <bits/stdc++.h>
using namespace std ;

typedef long long LL ;
const int N = 2010 ;
int mod ;

LL ksm( LL a , LL b )
{
	LL res = 1 , t = a % mod ;
	while( b ) {
		if( b&1 ) res = res * t % mod ;
		b = b >> 1 ;
		t = t * t % mod ;
	}
	return res ;
}
int t , n , M , K ;
LL C[N][N] , f[N][N] ;
int vis[N][N] ;
void pre_work( int n )
{
	for(int i = 0 ; i <= n ; i ++ ) {
		C[i][0] = 1 ;
		for(int j = 1 ; j <= i ; j ++ ) {
			C[i][j] = ( C[i-1][j] + C[i-1][j-1] ) % mod ;
		}
	}
}
LL dp( int n , int m ) // n个不同小球放入 m 个箱子，要求每个箱子中球数 <= K 
{
	if( n < 0 ) return 0 ;
	if( m == 1 ) return (n<=K) ;
	if( n == 0 ) return 1 ;
	if( vis[n][M-m] == K ) return f[n][M-m] ;
	vis[n][M-m] = K ;
	return f[n][M-m] = m*( dp(n-1,m) - dp(n-K-1,m-1)*C[n-1][K]%mod ) % mod ;
}

int main()
{
	scanf("%d%d" , &t , &mod ) ;
	pre_work(1000) ;
	while( t -- ) {
		scanf("%d%d" , &n , &M ) ;
		for(int i = 0 ; i <= n ; i ++ ) {
			for(int j = 0 ; j <= n ; j ++ ) vis[i][j] = 0 ;
		}
		LL ans = 0 , pw = ksm(M,n) ;
		for( K = 0 ; K <= n ; K ++ ) {
			ans = ( ans + pw - dp(n,M) ) % mod ;
		}
		printf("%lld\n" , (ans+mod)%mod ) ;
	}
	return 0 ;
}