How to get the correct output in Modulo (10^9 7) format?-CodePudding

I am working on this code challenge:

Problem Description

Given 2 integers x and n, you have to calculate x to the power of n, modulo 10^9 7 i.e. calculate (x^n) % (10^9 7).

In other words, you have to find the value when x is raised to the power of n, and then modulo is taken with 10^9 7.

a%b means the remainder when a divides b. For instance, 5%3 = 2, as when we divide 5 by 3, 2 is the remainder.

Note that 10^9 is also represented as 1e9.

Input format One line of input containing two space separated integers, x and n.

Output format Print the required answer.

Sample Input 1 100000000 2

Sample Output 1 930000007

Explanation 1 (10^8)^2 = 10^16

10^16 % (10^9 7) = 930000007

Constraints 0 <= x < 10^9

0 <= n < 10^5

Code

The following is my code:

import java.util.*;

class ModularExponentiation {
    // NOTE: Please do not modify this function
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int n = sc.nextInt();

        int ans = modularExponentiation(x, n);
        System.out.println(ans);
    }

    // TODO: Implement this method
    static int modularExponentiation(int x, int n) {
        int M = 1000000007;
        long a = (long) Math.pow(x, n);

        long b = a%M;

        return (int)b;
    }
}

When I run my code, it succeeds for the sample test case and an edge case, but fails for 3 base cases. How do I make my code succeed all test cases?

CodePudding user response：

Does this work?

    public static int modularExponentiation(int x, int n) {
        int modulo = 1000000007;
        if (n == 0) {
            return 1;
        } else if (n == 1) {
            return x % modulo;
        } else if (n == -1) {
            return 1 / x;
        }
        int p = modularExponentiation(x, n >> 1);
        long product = ((long) p * p) % modulo;
        return (int) (product * modularExponentiation(x, n & 1) % modulo);
    }