prima cepet

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
#include <string.h>

//  bool prime[1001];
int ngeprimain( long long n)
{
    long long i;
    for ( i=2; i*i<=n; i++)
    {
        if (n%i==0) return 0;
    } return 1;
}

int main()
{
long long pok,maha,hari,i;
//bool prime[1001];
long long mod=1000000007;

    scanf("%lld",&pok);
    while(pok)
    {
        scanf("%lld%lld",&maha,&hari);
        long long tot=maha;
        for(i=2;i<=hari;i++)
        {
        if(ngeprimain(i) )
        {
            tot*=maha;
            tot%=mod;
        } else
        {
            tot*=(maha-1);
            tot%=mod;
        }

        }
        printf("%lld\n",tot);
        pok--;
    } return 0;
}