#include<iostream>
using namespace std;
#define N 32
const int mol = 1234567891 ;
int n , K ;
int a[N][N] , b[N][N] , c[N][N] , d[N][N] , tmp[N][N];
void mult( int a[N][N] ,int b[N][N] )
{
int i , j , k ;
for ( i = 0 ;i <= K; i ++ )
{
for ( j = 0 ;j <= K ; j ++ )
{
tmp[i][j] = 0 ;
for ( k = 0 ; k <= K ; k ++ )
{
tmp [i][j] = ((long long )a[i][k] * b[k][j] % mol + tmp[i][j] ) % mol ;
}
}
}
for ( i = 0 ; i <= K ; i ++ )
{
for ( j = 0 ;j <= K ; j ++ )
a[i][j] = tmp[i][j] ;
}
}
void add ( int a[N][N], int b [N][N] )
{
int i , j;
for ( i = 0 ; i <= K ; i ++)
{
for ( j = 0 ;j <= K ; j ++ )
a[i][j] = ( ( long long ) a[i][j] + b[i][j] ) % mol;
}
}
void make ( int n )
{
if ( n == 0 )
return ;
make ( n / 2 );
int i , j , k;
for ( i = 0 ;i <= K ; i ++ ){
for ( j = 0 ;j <= K ; j ++ ){
d[i][j] = b[i][j];
if ( i == j )
d[i][j] = ( b[i][j] + 1 ) % mol ;
}
}
mult ( c , d );
mult ( b , b );
if ( n % 2 )
{
mult ( b , a );
add ( c , b );
}
}
int work ()
{
memset( a , 0 , sizeof ( a ));
memset( b, 0 , sizeof ( b ));
memset( c , 0 , sizeof ( c ));
memset( d , 0 , sizeof ( d ));
int i , j , k ;
for ( i = 0 ; i <= K ; i ++ )
{
b[i][i] = 1 ;
}
for ( i = 1 ; i <= K ; i ++ )
{
a[i][i] = i ;
a[i-1][i] = K - i + 1 ;
}
make( n );
return c[0][K];
}
int main()
{
int test;
scanf("%d",&test);
while ( test -- )
{
scanf("%d%d",&n,&K);
printf("%d\n",work());
}
return 0;
}
posted on 2009-08-17 19:55
Huicpc217 阅读(60)
评论(0) 编辑 收藏 引用