# include <iostream>
# include <fstream>
# include <vector>

using namespace std;

class Contor
{
private:
    long long val = 0;
    int MOD = 10000;

public:
    long long operator()() const;
    void operator+=( int a );
    void operator-=( int a );
    void operator*=( int a );
};

long long Contor::operator()() const
{
    return val;
}

void Contor::operator+=( int a )
{
    val = ( val + a % MOD ) % MOD;
}

void Contor::operator-=( int a )
{
    val = ( val + MOD - a % MOD ) % MOD;
}

void Contor::operator*=( int a )
{
    val = ( val * ( a % MOD ) ) % MOD;
}

vector<int> puterile_factorilor( int n )
{
    vector<int> s;
    int d, p;

    p = 0;
    while ( n % 2 == 0 ) {
        n /= 2;
        p ++;
    }

    if ( p != 0 )
        s.push_back( p );

    d = 3;
    while ( d * d <= n ) {
        p = 0;
        while ( n % d == 0 ) {
            n /= d;
            p ++;
        }

        if ( p != 0 )
            s.push_back( p );
        d += 2;
    }

    if ( n != 1 )
        s.push_back( 1 );

    return s;
}

int pow( int b, int p )
{
    Contor s, a;
    a += b;
    s += 1;

    while ( p > 0 ) {
        if ( p % 2 )
            s *= a();

        a *= a();
        p /= 2;
    }

    return s();
}

int main()
{
    ifstream fin( "multiplu2.in" );
    ofstream fout( "multiplu2.out" );

    int n, k, d, p;
    Contor s;
    s += 1;

    fin >> n >> k;

    for ( int x : puterile_factorilor( n ) ) {
        Contor aux;
        aux += pow( x + 1, k );
        aux -= pow( x, k );

        s *= aux();
    }

    fout << s();

    fin.close();
    fout.close();

    return 0;
}