如何正确实现模10^9+7格式的模幂运算得到正确输出

我当前正在完成如下代码挑战：

问题描述
给定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 <= x < 10^9
• 0 <= n < 10^5

原有问题代码 #

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

运行时样例和1个边界用例可以通过，但3个基础用例运行失败。

失败原因 #

1. 浮点数精度丢失：Math.pow的返回值是double类型，double仅能精确表示小于2^53的整数，当幂值超过这个范围时会自动截断精度，计算出的幂值本身就存在误差，后续取模结果必然错误。
2. 数值溢出风险：哪怕改用整数类型连乘计算完整幂值，long类型的最大存储值仅为约9e18，当x接近1e9、n较大时，x^n的数值远远超过long的存储上限，会发生溢出得到完全错误的结果。

修复方案 #

利用模运算的性质：(a * b) % mod = ((a % mod) * (b % mod)) % mod，不需要计算完整的x^n值，每次乘法运算后立刻对1e9+7取模，保证中间结果始终在long类型的安全存储范围内，同时搭配快速幂逻辑将时间复杂度降到O(logn)，兼顾正确性和效率，同时覆盖n=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);
    }

    static int modularExponentiation(int x, int n) {
        final int MOD = 1000000007;
        long result = 1;
        long base = x % MOD;
        
        while (n > 0) {
            // 当前指数为奇数时，将当前base乘入结果
            if ((n & 1) == 1) {
                result = (result * base) % MOD;
            }
            // base自乘取模，指数折半
            base = (base * base) % MOD;
            n >>= 1;
        }
        return (int) result;
    }
}

内容的提问来源于stack exchange，提问作者Ayan Dasgupta