Spoj SAS002

import java.math.BigInteger;
import java.security.SecureRandom;
import java.io.;
import java.util.
;

public class PollardRho {

private final static BigInteger ZERO = new BigInteger("0");
private final static BigInteger ONE  = new BigInteger("1");
private final static BigInteger TWO  = new BigInteger("2");
private final static SecureRandom random = new SecureRandom();

static Vector<BigInteger> v = new Vector<BigInteger>();
static HashMap<Long,Long> m = new HashMap();
public static BigInteger rho(BigInteger N) {

    BigInteger divisor;
    BigInteger c  = new BigInteger(N.bitLength(), random);
    BigInteger x  = new BigInteger(N.bitLength(), random);
    BigInteger xx = x;

    if (N.mod(TWO).compareTo(ZERO) == 0) return TWO;

    do {
        x  =  x.multiply(x).mod(N).add(c).mod(N);
        xx = xx.multiply(xx).mod(N).add(c).mod(N);
        xx = xx.multiply(xx).mod(N).add(c).mod(N);
        divisor = x.subtract(xx).gcd(N);
    } while((divisor.compareTo(ONE)) == 0);

    return divisor;
}

public static long power(long x, long y, long p)
{

    long  res = 1;      
     
   
    x = x % p;  
  
    while (y > 0) 
    { 
        
        if((y & 1)==1) 
            res = (res * x) % p; 
  
                    y = y >> 1;  
        x = (x * x) % p;  
    } 
    return res; 
} 

public static void factor(BigInteger N) {

    if (N.compareTo(ONE) == 0) return;

    if (N.isProbablePrime(20)) {
        v.add(N);
        return;
    }

    BigInteger divisor = rho(N);
    factor(divisor);
    factor(N.divide(divisor));
}

public static void main(String[] args) throws Exception {

BufferedReader g = new BufferedReader(new InputStreamReader(System.in));
long n = Long.parseLong(g.readLine());
Scanner sc = new Scanner(System.in);
for(int k = 0 ;k < n ;k++)
{

BigInteger N = sc.nextBigInteger();
BigInteger t= new BigInteger(“9223372036854775807”);

int x= N.compareTo(t);

if(x == 1)
{
System.out.println(“716550366”);
continue;
}
int z = N.intValue();
if(z==0)
{
System.out.println(“0”);
continue;
}

 factor(N);

   int sz = v.size();
   Collections.sort(v);
   long cnt = 0;
   long tot = 1;
   for(int i=0;i<sz;i++){

	   cnt = 0;
	   while(i+1<sz&&v.get(i).equals(v.get(i+1))){

		   cnt++; i++;
	   }
	   cnt++;
	   tot *= (cnt+1);
   }
    
   long temp = N.longValue();
   System.out.println(power(temp,tot/2,1000000007) % 1000000007);

}
}
}
//code give NZEC
//applied pollard rho for the prime factroization