Find value of n^k modulo 10^7 + 7

Giving int n and k. Find the value of n^k modulo 10^7+7.
I 've been trying to do this problem in different ways using the properties of modulo as ( a * b) % c = ( ( a % c ) * ( b % c ) ) % c . Below is my code. Also, I am a new user, if I missed anything please let me know.

int res = 1;
int modulo = (int) Math.pow(10,7)+7;
//( a * b) % c = ( ( a % c ) * ( b % c ) ) % c
System.out.println(modulo);
for (int i = 1 ; i <= k; i++){
    res = ((res%modulo)*(n%modulo))%modulo;
   
}

return res;

Both solutions below run in O(log k), unlike e.g. the code in the question (O(k)), and the answer by WJS using BigInteger. WJS's code starts getting slow when k is 6 digits. Both solutions below returns immediately even when k is Long.MAX_VALUE.

In the description in this answer, a^b means exponentiation, not bitwise xor.

You're on the right path using

(a * b) % c = ((a % c) * (b % c)) % c

What you're missing is

a ^ (b + c) = (a ^ b) * (a ^ c)

<h3>Recursive solution</h3>

Since the goal is to calculate (n^k) % (10^7 + 7), you can calculate this in O(log k) time by recursively splitting k.

E.g. if k = 15 then split like this

n^15  =  n^8 * n^7
      =  (n^4 * n^4) * (n^4 * n^3)
      =  ...

With modulo that means

(n^15) % m  =  ((n^8) % m * (n^7) % m) % m
            =  ...

If you create a method for calculating (n^k) % m

int calc(int n, int k, int m)

then with k = 15, calc(n, 15, m) calls calc(n, 8, m) and calc(n, 7, m) recursively. With memoization, the result has O(log k) time complexity.

public static int calc(int n, long k) {
	if (n < 0 || k < 0)
		throw new IllegalArgumentException();
	if (n == 0)
		return 0;
	if (k == 0)
		return 1;
	return calc0(n, k, new HashMap<>());
}

private static int calc0(int n, long k, Map<Integer, Integer> cache) {
	Integer cachedValue = cache.get(k);
	if (cachedValue != null)
		return cachedValue;
	int result;
	if (k == 1)
		result = n % MODULO;
	else
		result = (int) ((long) calc0(n, k / 2, cache) * calc0(n, k - k / 2, cache) % MODULO);
	cache.put(k, result);
	return result;
}
private static final int MODULO = 10000007;

<h3>Bitwise solution</h3>

If you don't like recursion and memoization, you can use bit manipulation. This is actually slightly more efficient than the recursive approach, sometimes using fewer multiplication and remainder operations.

I won't explain it. See if you can figure out how that works.

public static int calc(int n, long k) {
	if (n < 0 || k < 0)
		throw new IllegalArgumentException();
	int e = n % MODULO;
	int r = ((k & 1) != 0 ? e : 1);
	for (long i = k >>> 1; i != 0; i >>>= 1) {
		e = (int) ((long) e * e % MODULO);
		if ((i & 1) != 0)
			r = (int) ((long) r * e % MODULO);
	}
	return r;
}
private static final int MODULO = 10000007;

<h3>Test</h3>

System.out.println(calc(282828,292929));
System.out.println(calc(123456789,987654321));
System.out.println(calc(Integer.MAX_VALUE, Long.MAX_VALUE));

Output

6154601
5111924
5910478

This is easiest. You can use it to check your other answers.

		System.out.println(fnc(282828,292929));
        System.out.println(yours(282828,292929));
	
	
	public static BigInteger fnc(int n, int k) {
		
		int modulo = (int) Math.pow(10, 7) + 7;
		BigInteger res = BigInteger.valueOf(n).pow(k)
				.mod(BigInteger.valueOf(modulo));
		return res;
	}

And here is your solution. You only needed to use long's

	public static long yours(long n, long k) {
		long res = 1;
		int modulo = (int) Math.pow(10, 7) + 7;
		// ( a * b) % c = ( ( a % c ) * ( b % c ) ) % c

        // pull out n % modulo since n never changes.
		long nmod = n% modulo;
		long res = nmod%modulo;
		for (int i = 1; i < k; i++) {
			res = ((res% modulo)*(nmod))%modulo;
		}
		return res;
	}

They both print

6154601
6154601

Slight optimizations.

• pull out n % modulo as nmod. Just compute once.
• since 1 % modulo is 1 first time thru, just initialize res to nmod % modulo. Then just iterate to i < k times.