static BigInteger powerMod(BigInteger base, long exp, BigInteger mod){
		int n = (int)log2(exp);
		BigInteger[] a = new BigInteger[n+1];
		a[0] = base.mod(mod);
		for(int i = 1; i <= n; i++){
			a[i] = a[i-1].pow(2).mod(mod);
		}
		BigInteger ans = new BigInteger("1");
		for(int i = n; i >= 0; i--){
			long p = (long)Math.pow(2, i);
			if(exp >= p){
				exp -= p;
				ans = ans.multiply(a[i]);
			}
		}
		return ans.mod(mod);
	}