#include<bits/stdc++.h>
typedef long long LL ;
const int N = 1e6 + 10 , INF = 1e9 + 7 ;
using namespace  std ;
int p ;
LL  n , m , k , tt ;
int a[ N ] , af[ N ] , b[ N ] , bf[ N ] ;

LL qmi( LL di , LL mi ){
    LL res = 1 ;
    while( mi  ){
        if( mi & 1 ){
            res *= di ; res %= p ;
        }
        di *= di ; di %= p ;
        mi /= 2 ;
    }
    di *= di ; di %= p ;
    mi /= 2 ;
    return res % p ;
}

void AC(){
//    cin >> n ;
//    for( int i = 1 ; i <= n ; i ++ ){
//        cin >> a[ i ] ;
//        if( i >= 2 ){
//            af[ i - 1 ] = a[ i ] - a[ i - 1 ] ;
//        }
//    }
//
//    for( int i = 1 ; i <= n ; i ++ ){
//        cin >> b[ i ] ;
//        if( i >= 2 ){
//            bf[ i - 1 ] = b[ i ] - b[ i - 1 ] ;
//        }
//
//    }
    cin >> p >> k >> tt ;
    int ans = p - qmi( k , tt ) ;
    cout << ans << endl;
    return ;
}

int main(){
    ios::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
    int t  = 1 ;
    //cin >> t ;
    //cout << ( 1296 * 216 ) % 11 << endl ;
    while( t-- ){
        AC() ;
    }
    return 0 ;
}