#include<bits/stdc++.h>
#define int long long
#define p pair<int, int>
#define endl '\n'
using namespace std;
int pow1(int x, int y, int z){
if (y == 0){
return 1;
}
if (y % 2 == 0){
return pow1(x*x % z, y/2, z);
}
return pow1(x, y-1, z)*x % z;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int b, n, m;
cin >> b >> n >> m;
if (m == 1){
cout << 0 << endl;
}else if (n == 1){
cout << 1 << endl;
}else if (m >= (int)pow(b, min(n, 30LL))){
cout << 0 << endl;
}else{
int l = -1, r = n;
while (r-l > 1){
int m1 = (l+r)/2;
if (pow1(b, m1, m) == 0){
r = m1;
}else{
l = m1;
}
}
if (b == 2 && r == n){
cout << n-1 << endl;
}else{
cout << r << endl;
}
}
return 0;
}