题解 | #kotori和气球#

#include<stdio.h>
int main(){
    
    int n,m;
    const int mod = 109;
    scanf("%d %d",&n,&m);
    long long cnt = n;
    for(int i = 0;i<m-1;i++){
        cnt *= (n-1); 
        cnt = cnt % mod;
    }
    printf("%lld",cnt);
    return 0;