#include<stdio.h>
int main()
{
    int n,m,k,i;
    scanf("%d%d",&n,&m);
        k=n; 
    for(i=1;i<m;i++)
    {
 
            k*=(n-1);
            k%=109;
    }
    printf("%d",k);
    return 0;
}
一共有n种气球，然后要求是一排排多少的问题，
如果一排排一种气球，那么有n种气球，所以k==n；
当m>1的时候，例如：当m=2的时候，k=n*（n-1）；
当m=3的时候，k=n*(n-1)*(n-1);
.......
k=n*(n-1)*(n-1).....(n-1)中间有m个，每次模109防止溢出