program stirling;
const modulo=98999;
type mat=array[1..200,1..200]of longint;
var sI,sII:mat;
    x,n,m,i,t:integer;
    f,g:text;
procedure CreareSpetaI;
var i,j:integer;
begin
sI[1,1]:=1;
for i:=2 to n do
 for j:=1 to i do
 sI[i,j]:=(sI[i-1,j-1]-(i-1)*sI[i-1,j]) mod modulo;
end;

procedure CreareSpetaII;
var i,j:integer;
begin
sII[1,1]:=1;
for i:=2 to n do
 for j:=1 to i do
 sII[i,j]:=(sII[i-1,j-1]+j*sII[i-1,j]) mod modulo;
end;

begin
assign(f,'stirling.in');reset(f);
assign(g,'stirling.out');rewrite(g);
CreareSpetaI;
CreareSpetaII;
readln(f,t);
for i:=1 to t do
 begin
 readln(f,x,n,m);
 if x=1 then writeln(g,sI[n,m])
        else writeln(g,sII[n,m]);
 end;




close(f);close(g);
end.