var s1,s2:array[0..205,0..205] of longint;
t,i,j,x,n,m:longint;
f,g:text;
begin
assign(f,'stirling.in');
assign(g,'stirling.out');
reset(f);rewrite(g);
s1[0,0]:=1;
s2[0,0]:=1;
for i:=1 to 200 do
    for j:=1 to i do
        begin
        s1[i,j]:=(s1[i-1,j-1]+(i-1)*s1[i-1,j]) mod 98999;
        s2[i,j]:=(s2[i-1,j-1]+j*s2[i-1,j]) mod 98999;
        end;
readln(f,t);
for i:=1 to t do
    begin
    readln(f,x,n,m);
    if x=1 then
       if (n-m) mod 2=0 then
          writeln(g,s1[n,m])
       else
           writeln(g,-s1[n,m])
    else
        writeln(g,s2[n,m]);
    end;
close(f);close(g);
end.