vector <long long> v;
long long p[100 * 1000 + 100];

int lastDigitsFactorial(std::string N, int k)
{
    using namespace std;

    p[0] = 1;
    for (int i = 1; i < 100 * 1000 + 10; i++)
        p[i] = (2 * p[i - 1]) % (100 * 1000);


    long long n = stoll(N);
    v.push_back(1);
    long long t2 = 0, l = 1;
    for (long long i = 1; i <= 100 * 1000; i++)
    {
        long long j = i;
        while (j % 2 == 0)
        {
            t2++;
            j /= 2;
        }
        while (j % 5 == 0)
        {
            t2--;
            j /= 5;
        }
        l = (long long)(l * j) % (long long)(100 * 1000);
        v.push_back((long long)(l * p[t2]) % (long long)(100 * 1000));
    }

    long long ans = 1;
    for (long long i = 0; i < int(n / (100 * 1000)); i++)
        ans = (long long)(ans * v[100 * 1000]) % (long long)(100 * 1000);
    ans = (long long)(ans * v[n % (100 * 1000)]) % (long long)(100 * 1000);

    return ans;
}