#include <iostream>
#include <vector>

using namespace std;
int mod, np;
long long p[32010];

class Powerit
{
public:
    Powerit(){}
    long long mul(long long x, long long k)
    {
        if (k == 1) return x;
        long long kk = mul(x, k/2);
        if (k % 2 == 0)
            return ((kk * kk) % mod);
        else
           return ((((kk * kk) % mod) * x) % mod);
    }

    int calc(int n, int k, int m)
    {
        mod = m;
        int cp = m;
        // EFT with m
        int x = 2;
        while (x * x <= cp) {
            long long kk = 1;
            while (m % x == 0)
            {
                kk*=x;
                m = m/x;
            }
            if (kk > 1)
            {
                kk = (kk / x)*(x - 1);
                np++;
                p[np] = kk;
            }
            x++;
        }
        if (m > 1)
        {
            np++;
            p[np] = m;
        }
        m = cp;
        long long kk = 1;
        for (int i = 1; i <= np; i++)
             kk *= p[i];

        // 2^k - 1
        long long mu = 1;
        for (int i = 1; i <= k; i++)
            mu = (mu * 2) % kk;
        mu = (mu - 1) % kk;
        //
        long long sum = 0;
        for (int i = 1; i <= n; i++)
        {
            sum = (sum + mul(i % mod, mu)) % mod;
        }
        return sum;
    }
};