首先 $f_0=0$，然后特判 $k \le 1$ 的情况。

直接建立一张有向图，$i \to ki$ 表明 $f_i$ 能唯一确定 $f_{ki}$，由于所有点的出度为 $1$，这张图一定是若干个 $a \to b \to \ldots \to m \to n \to \ldots \to z \to m \to \ldots$ 的 $\rho$ 形（实际上是若干个环），庶出 $\rho$ 形的个数 $x$，答案即为 $n^{x-1}$，因为 $n$ 个 $\rho$ 形起点处的 $f$ 值唯一确定了整个序列，并且 $f_0=0$。

实际上，进一步的分析表明，求出 $k$ 对 $p$ 的阶 $\delta_p(k)$，答案即为 $n^{\frac{n-1}{\delta_p(k)}}$。

#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
int power(int b, int k)
{
    if (k == 0) return 1;
    if (k == 1) return b;
    long long s = power(b, k >> 1);
    s = s * s % P;
    if (k & 1) s = s * b % P;
    return s;
}
int main()
{
	int n, m;
	cin >> n >> m;
    if (m <= 1)
    {
        cout << power(n, n - 1 + m) << endl;
        return 0;
    }
    long long k = m, l = 1;
    while (k != 1) k = k * m % n, l++;
    cout << power(n, (n - 1) / l) << endl;
	return 0;
}