题解 | #kotori和气球#

1.当m等于1时，随便放一种气球，有n种放法

2.当m不等于1时 第一个位置有n种选择，第二个位置有n-1种选择，（因为它不能与第一个气球相同）。 同理第三个气球依然是n-1种选择，所以总排列方法数way=n * (n-1)^(m-1)

乘法的模运算：

(a×b) mod m=[(a mod m)×(b mod m)] mod m 这条性质告诉我们，在进行乘法后取模的结果，等同于先对乘数分别取模后再乘法取模。因此，哪怕我们在循环的每一步都取模，最终结果也不会改变。边循环边取模是一个 有效且正确的技巧.

#include<iostream>

using namespace std;
#define mod 109
typedef long long LL;
int main()
{
    int n,m;
    cin >> n >> m;
    LL way = n;
    for(int i=0;i < m-1;i++)
    {
        way *= (n-1);
        way %= mod;
    }
    cout << way << endl;
    return 0;
}