第一个写JAVA题解

import java.util.Scanner;

public class 越狱 {
    /**
     * 解题思路大致如下：
     * 首先思考所有方案数：mn=m*m(n-1)
     * 所有不发生越狱的方案数：m*(m-1)(n-1)种
     * 所以发生越狱的方案数：m*m(n-1)-m*(m-1)(n-1)=m*(m(n-1)-(m-1)(n-1))
     * 分别对m(n-1)和(m-1)(n-1)快速幂即可
     */
    static long mod = 100003;

    public static long pow(long x, long y) {
        long ans = 1;
        long d = x%mod;
        while(y>0){
            if(y%2==1) {
                ans = (ans * d) % mod;
            }
            y=y/2;
            d=(d*d)%mod;
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long m = in.nextLong();
        long n = in.nextLong();
        long tot = pow(m,n);
        tot -= m*pow(m-1,n-1)%mod;
        if(tot<0) tot+=mod;
        System.out.println(tot);
    }
}