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

typedef long long LL ;
const int N = 1010 ;
// 妙妙题
// 容斥可以完成这个计数
// 观察dp式子，m每减1,n会减k，所以复杂度是 n/k 的 

int T , mod ;
LL C[N][N] ;

unordered_map<int,LL> f[N] ;
int K , n , m ;
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( f[n].count(m) ) return f[n][m] ;
//	printf("f[%d][%d] = %lld\n" , n , m , f[n][m] ) ;
	return f[n][m] = m*( dp(n-1,m) - dp(n-K-1,m-1)*C[n-1][K]%mod ) % mod ;
//	return f[n][m] ;
}

int main()
{
	scanf("%d%d" , &T , &mod ) ;
	for(int i = 0 ; i <= 1000 ; 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 ;
		}
	}
	while( T -- ) {
		scanf("%d%d" , &n , &m ) ;
		LL sum = 0 , pw = 1 ;
		for( K = 1 ; K < n ; K ++ ) {
			for(int i = 0 ; i <= n ; i ++ ) f[i].clear() ;
			sum = ( sum + dp(n,m) ) % mod ;
//			printf("K = %d , (%d,%d) = %lld\n" , K , n , m , dp(n,m) ) ;
			pw = pw * m % mod ;
		}
		pw = pw * m % mod ;
		printf("%lld\n" , (pw*n%mod - sum + mod ) % mod ) ;
	}
	return 0 ;
}