差分序列

program ProblemB;

const
	inf	=	‘‘;
	ouf	=	‘‘;
	MaxK	=	101;
	maxLen	=	100;
	radix	=	10000;

type
	Bignum	=	array [ 0 .. MaxLen ] of longint;

var
	Com	:	array [ 0 .. MaxK , 0 .. MaxK ] of Bignum;
	F	:	array [ 0 .. MaxK ] of Bignum;
	N	:	Bignum;
	K	:	longint;

procedure openFile;
    begin
	assign ( input , inf ) ; reset ( input );
	assign ( output , ouf ) ; rewrite ( output );
    end;

procedure closeFile;
    begin
	close ( input );
	close ( output );
    end;

procedure init;
    var
	s	:	string;
	ch	:	char;
    begin
	S := ‘‘ ; read ( ch );
	while ch <> ‘ ‘ do
	begin
		S := S + ch;
		read ( ch );
	end;
	readln ( K );

	fillchar ( N , sizeof ( N ) , 0 );
	while S <> ‘‘ do
	begin
		inc ( N [ 0 ] );
		if length ( S ) > 4 then
		begin
			val ( copy ( S , length ( S ) - 3 , 4 ) , N [ N [ 0 ] ] );
			delete ( S , length ( S ) - 3 , 4 );
		end else
		begin
			val ( S , N [ N [ 0 ] ] );
			S := ‘‘;
		end;
	end;
    end;

function max ( a , b : longint ) : longint;
    begin
	if a > b then max := a else max := b;
    end;

procedure add ( var A , B , C : Bignum );
    var
	i , x	:	longint;
	tmp	:	Bignum;
    begin
	fillchar ( tmp , sizeof ( tmp ) , 0 );
	tmp [ 0 ] := max ( A [ 0 ] , B [ 0 ] ) + 1 ; x := 0;
	for i := 1 to tmp [ 0 ] do
	begin
		x := A [ i ] + B [ i ] + x div radix;
		tmp [ i ] := x mod radix;
	end;
	C := tmp;
	while ( C [ 0 ] > 1 ) and ( C [ C [ 0 ] ] = 0 ) do dec ( C [ 0 ] );
    end;

procedure sub ( var A , B , C : Bignum );
    var
	i , x	:	longint;
	tmp	:	Bignum;
    begin
	fillchar ( tmp , sizeof ( tmp ) , 0 );
	tmp [ 0 ] := A [ 0 ] ; x := 0;
	for i := 1 to tmp [ 0 ] do
	begin
		x := A [ i ] - B [ i ] + x + radix;
		tmp [ i ] := x mod radix;
		x := x div radix - 1;
	end;
	C := tmp;
	while ( C [ 0 ] > 1 ) and ( C [ C [ 0 ] ] = 0 ) do dec ( C [ 0 ] );
    end;

procedure mul ( var A , B , C : Bignum );
    var
	i , j , x	:	longint;
	tmp		:	Bignum;
    begin
	fillchar ( tmp , sizeof ( tmp ) , 0 );
	tmp [ 0 ] := A [ 0 ] + B [ 0 ];
	for i := 1 to A [ 0 ] do
	begin
		x := 0;
		for j := 1 to B [ 0 ] + 1 do
		begin
			x := A [ i ] * B [ j ] + tmp [ i + j - 1 ] + x div radix;
			tmp [ i + j - 1 ] := x mod radix;
		end;
	end;
	C := tmp;
	while ( C [ 0 ] > 1 ) and ( C [ C [ 0 ] ] = 0 ) do dec ( C [ 0 ] );
    end;

procedure divK ( var num : Bignum ; k : longint );
    var
	i , x	:	longint;
    begin
	x := 0;
	for i := num [ 0 ] downto 1 do
	begin
		x := x * radix + num [ i ];
		num [ i ] := x div k;
		x := x mod k;
	end;
	while ( num [ 0 ] > 1 ) and ( num [ num [ 0 ] ] = 0 ) do dec ( num [ 0 ] );
    end;

procedure prepare;
    var
	i , j	:	longint;
    begin
	fillchar ( Com , sizeof ( Com ) , 0 );
	for i := 0 to MaxK do
	begin
		Com [ i , 0 , 0 ] := 1;
		Com [ i , 0 , 1 ] := 1;
		for j := 1 to i do
			add ( Com [ i - 1 , j - 1 ] , Com [ i - 1 , j ] , Com [ i , j ] );
	end;
    end;

procedure Main;	
    var
	i , j	:	longint;
	one	:	Bignum;
	N_	:	Bignum;
	pow	:	Bignum;
	tmp	:	Bignum;
    begin
	fillchar ( one , sizeof ( one ) , 0 );
	one [ 0 ] := 1 ; one [ 1 ] := 1;

	F [ 0 ] := N;
	add ( N , one , N_ );
	pow := N_;

	for i := 1 to K do
	begin
		mul ( pow , N_ , pow );
		sub ( pow , one , F [ i ] );

		for j := 0 to i - 1 do
		begin
			mul ( F [ j ] , Com [ i + 1 , j ] , tmp );
			sub ( F [ i ] , tmp , F [ i ] );
		end;

		divK ( F [ i ] , i + 1 );
	end;
    end;

function hex ( x : longint ) : string;
    var
	s	:	string;
    begin
	str ( x + radix , s );
	hex := copy ( s , 2 , 4 );
    end;

procedure out;
    var
	i	:	longint;
	answer	:	Bignum;
    begin
	answer := F [ K ];

	write ( answer [ answer [ 0 ] ] );
	for i := answer [ 0 ] - 1 downto 1 do
		write ( hex ( answer [ i ] ) );
	writeln;
    end;

var
	data	:	longint;

begin
	openFile;

	prepare;
	readln ( data );
	for data := 1 to data do
	begin
		init;
		Main;
		out;
	end;

	closeFile;
end.