POWER PASCAL

const k = 1000000009;
var     t:longint;
i:longint;
y,a,n:int64;
function luythua(a,n:int64):int64;
var s:int64;
begin
        if n=0 then exit(1)
        else
        begin
                s:=luythua(a,n div 2);
                s:=(s*s) mod k;
                if n mod 2=0 then exit(s)
                else exit((s*(a mod k))mod k);
        end;
end;
begin
    assign(input,'power.inp');reset(input);
    assign(output,'power.out');rewrite(output);
    readln(t);
    for i:=1 to t do
    begin
            readln(a,n);
            y:=luythua(a,n);
            writeln(y);
    end;
end.