program stirling;
const modulo=98999;
type mat=array[0..200,0..200]of longint;
var sI,sII:mat;
    x,n,m,i,t:integer;
    f,g:text;
procedure Creare;
var i,j:integer;
begin
sI[0,0]:=1;
SII[0,0]:=1;
for i:=1 to 200 do
for j:=1 to i do
   begin
   sI[i,j]:=(sI[i-1,j-1]-(i-1)*sI[i-1,j])mod modulo;
   sII[i,j]:=(sII[i-1,j-1]+j*sII[i-1,j])mod modulo;
   end;
end;
begin
assign(f,'stirling.in');reset(f);
assign(g,'stirling.out');rewrite(g);
Creare;
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.