题解 | #kotori和气球#

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        long ans = n;
        for(int i = 1;i<m;i++){
            ans=(ans*(n-1))%109;
        }
        if(n==1&&m!=1) System.out.println(0);
        else System.out.println(ans);
    }
}

每次都取模，防止数据过大。