牛客对应题目链接：kotori和气球 (nowcoder.com)

---

一、分析题目

简单的排列组合问题，结果等于 n 与 m-1 个 n - 1 的乘积。

---

二、代码

//值得学习的代码
#include <iostream>

using namespace std;

const int MOD = 109;

int main()
{
    int n, m;
    cin >> n >> m;
    int ret = n;
    for(int i = 0; i < m - 1; i++)
    {
        ret = ret * (n - 1) % MOD;
    }
 
    cout << ret << endl;
 
    return 0;
}

---

三、反思与改进

根据样例推导，我以为每一种气球只能放置一个位置，然后进行排列组合，但其实忽略了一种情况，这里只需要相同种类不相邻即可。