C++ :

#include <cstdio>
typedef long long ll;
int main(){
    int T; if(scanf("%d", &T) != 1) return 0;
    while(T--){
        ll a, b; scanf("%lld %lld", &a, &b);
        ll r = 1 % 9907, base = a % 9907;
        while(b > 0){
            if(b & 1) r = r * base % 9907;
            base = base * base % 9907;
            b >>= 1;
        }
        printf("%lld\n", r);
    }
    return 0;
}