import java.util.*;
class Matrix{
static final int M = 1234567891;
public int a[][] ;
public int n ;
Matrix( int _n , int val){
int i , j ;
n = _n ;
a = new int[n][n];
for ( i = 0 ; i < n ; i ++ )
{
for ( j = 0 ;j < n ;j ++ )
if ( i == j )
a[i][j] = val;
else
a[i][j] = 0 ;
}
}
Matrix mult ( Matrix b ){
Matrix ret = new Matrix(n,0);
int i , j , k ;
for ( i = 0 ; i < n ; i ++ )
{
for ( j = 0 ; j < n ; j ++ )
{
for ( k = 0 ; k < n ; k ++ )
ret.a[i][j] = (int)(((long)a[i][k] * b.a[k][j] + ret.a[i][j]) % M);
//(int)必须要 使用
}
}
return ret;
}
Matrix pow ( int p ){
Matrix ret = new Matrix ( n , 1 );
Matrix t = this ;
while ( p > 0 )
{
if ( (p & 1) != 0 ) ret = ret .mult(t);
p >>= 1 ;
//ret.show();
t = t.mult(t);
}
return ret;
}
void show()
{
int i , j ;
for ( i = 0 ; i < n ; i ++)
{
for ( j = 0 ; j < n ; j ++)
{
System.out.print(a[i][j]+ " ");
}
System.out.println();
}
System.out.println();
}
}
public class Main{
public static void main(String [] args)throws Exception
{
Scanner cin = new Scanner ((System.in));
int test = cin.nextInt();
int n , K ;
while ( test > 0 )
{
test -- ;
n = cin.nextInt();
K = cin.nextInt();
Matrix g = new Matrix ( 2 * ( K + 1 ) , 1 );
for ( int i = 0 ; i <= K ; i ++ )
{
g.a[i][i] = i ;
if ( i > 0 )
g.a[i][i-1] = K - i + 1;
}
for ( int i = 0 ; i <= K ; i ++ ){
g.a[K + 1 + i ] [ i ] = 1;
}
Matrix gg = g.pow(n);
//g.show();
//gg.show();
System.out.println((long)gg.a[2*K+1][1]*K%1234567891);
}
}
}
posted on 2009-08-18 19:34
Huicpc217 阅读(100)
评论(0) 编辑 收藏 引用 所属分类:
JAVA