// SFUNC
// SuperFunction
// Author: Konstantin Sokol
// Complexity : O( sqrt(N) + 2^11 * K ^ 2 * log N * log M )
 
#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
const int MAXK = 10;
 
long long n, mod;
int k; 
vector< long long > p;
 
struct Matrix
{
    long long a[ MAXK + 2 ][ MAXK + 2 ];
    Matrix()
    {
        for ( int i = 0; i < MAXK + 2; i++ )
            for ( int j = 0; j < MAXK + 2; j++ )
                a[i][j] = 0;
    }
};
 
int gcd( int a, int b )
{
    if ( a != 0 ) return gcd( b % a, a ); return b;
}
 
long long mul1( long long a, long long b )
{
    long long result = 0;
    a %= mod;
    b %= mod;
    if ( a > b ) swap( a, b );
    while ( a )
    {
        if ( a % 2 )
        {
            result += b;
            if ( result >= mod ) result -= mod;
            a -= 1;
        }
        a /= 2;
        b += b;
        if ( b >= mod ) b -= mod;
    }
    return result;
}
 
long long pow1( long long a, long long p )
{
    long long result = 1;
    while ( p )
    {
        if ( p % 2 )
        {
            result = mul1( result, a );
            p -= 1;
        }
        p /= 2;
        a = mul1( a, a );
    }
    return result;
}
 
Matrix operator*( Matrix a, Matrix b )
{
    Matrix c;
    for ( int i = 0; i < k + 2; i++ )
        for ( int j = 0; j < k + 2; j++ )
            for ( int l = 0; l < k + 2; l++ )
                ( c.a[i][j] += mul1( a.a[i][l], b.a[l][j] ) ) %= mod;
    return c;
}
 
Matrix p2[ 40 ];
 
long long fun( long long n )
{
    vector< long long > v( k + 2, 0 );
    v[0] = 1;
    for ( int i = 0; i < 40; i++ )
    {
        if ( n % 2 == 0 )
        {
            n /= 2;
            continue;
        }
        n /= 2;
        vector< long long > res( k + 2, 0 );
        for ( int j = 0; j < k + 2; j++ )
            for ( int l = 0; l < k + 2; l++ )
                ( res[j] += mul1( p2[i].a[l][j], v[l] ) ) %= mod;
        v = res;
    }
    return v.back();
}
 
long long ans = 0;
 
void rec( int pos, long long a, long long sgn )
{
    if ( pos == p.size() )
    {
        ans = ( ans + sgn * mul1( pow1( a, k ), fun( n / a ) ) + mod ) % mod;
        return;
    }
    rec( pos + 1, a, sgn );
    rec( pos + 1, a * p[pos], -sgn );
}
 
int main (int argc, const char * argv[])
{
    cin >> n >> k >> mod;
    //---------Factorization of N------------ 
    long long nn = n;
    for ( long long i = 2; i * i <= n; i++ )
    {
        if ( nn % i == 0 )
        {
            p.push_back( i );
            while ( nn % i == 0 ) nn /= i;
        }
    }
    if ( nn != 1 ) p.push_back( nn );
    //---------Getting p2[0]-----------------
    for ( int j = 0; j < k + 1; j++ ) p2[0].a[0][j] = 1;
    for ( int j = 1; j < k + 1; j++ )
        for ( int i = 1; i < k + 1; i++ )
            p2[0].a[i][j] = ( p2[0].a[i][j - 1] + p2[0].a[i - 1][j - 1] ) % mod;
    for ( int i = 0; i < k + 1; i++ ) p2[0].a[i][k + 1] = p2[0].a[i][k];
    p2[0].a[k + 1][k + 1] = 1;
    //---------Calculating p2[]--------------
    for ( int i = 1; i < 40; i++ ) p2[i] = p2[i - 1] * p2[i - 1];
 
    rec( 0, 1, 1 );
 
    cout << ans << "\n"; 
 
    return 0;
}