如何以模（10^9 7）格式获得正确的输出？

Question

我正在进行代码挑战：

问题描述

给定2个整数x和n，您必须计算x的n次方，模10^9 7，即计算（x^n）%（10^9 7）。

换句话说，你必须找到当x提高到n的幂时的值，然后用10^9 7取模。

当a除以b时，a%b表示余数。例如，5%3=2，当我们将5除以3时，2是余数。

注意10^9也表示为1e9。

输入格式一行输入，包含两个空格分隔的整数x和n。

输出格式打印所需的答案。

样本输入1 100000000 2

样本输出1 930000007

解释1 (10^8)^2 = 10^16

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

约束0

0

代码

以下是我的代码：

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;
    }
}

当我运行代码时，它在样本测试用例和边缘用例中成功，但在3个基本用例中失败。如何使我的代码在所有测试用例中成功？

Answer 1

这行吗？

    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);
    }