#include <bits/stdc++.h>
using namespace std;
#define ll long long
// #define mod 1000000007
ll mod, m;
struct matran
{
        ll a[2][2];
        void print()
        {
                for (ll i = 0; i < 2; i++)
                {
                        for (ll j = 0; j < 2; j++)
                                cout << a[i][j] << " ";
                        cout << '\n';
                }
        }
};
matran mot;
struct cap
{
        ll u, u_plus_1;
        void print()
        {
                cout << u << " " << u_plus_1 << '\n';
        }
};
ll f(ll a, ll n, ll mod)
{
        ll res = a, ans = 0;
        while (n)
        {
                if (n % 2)
                        ans = (ans + res) % mod;
                res = (res + res) % mod;
                n /= 2;
        }
        return ans;
}
ll po(ll a, ll n)
{
        ll res = a, ans = 1;
        while (n)
        {
                if (n % 2)
                        ans = f(ans, res, mod);
                res = f(res, res, mod);
                n /= 2;
        }
        return ans;
}
ll aka(ll p, ll alpha)
{
        if (alpha == 0)
                return 1;
        if (alpha == 1)
                return (p + 1) % mod;
        if (alpha % 2 == 1)
                return (f(p, aka(p, alpha - 1), mod) + 1) % mod;
        if (alpha % 2 == 0)
                return (f((po(p, alpha / 2) + 1), ((aka(p, alpha / 2) - 1 + mod) % mod), mod) + 1) % mod;
}
cap prod1(cap pp, matran X)
{
        cap ans;
        ans.u = (f(pp.u, X.a[0][0], mod) + f(pp.u_plus_1, X.a[1][0], mod)) % mod;
        ans.u_plus_1 = (f(pp.u, X.a[1][0], mod) + f(pp.u_plus_1, X.a[1][1], mod)) % mod;
        return ans;
}
matran prod(matran A, matran B)
{
        matran anss;
        anss.a[0][0] = (f(A.a[0][0], B.a[0][0], mod) + f(A.a[0][1], B.a[1][0], mod)) % mod;
        anss.a[0][1] = (f(A.a[0][0], B.a[0][1], mod) + f(A.a[0][1], B.a[1][1], mod)) % mod;
        anss.a[1][0] = (f(A.a[1][0], B.a[0][0], mod) + f(A.a[1][1], B.a[1][0], mod)) % mod;
        anss.a[1][1] = (f(A.a[1][0], B.a[0][1], mod) + f(A.a[1][1], B.a[1][1], mod)) % mod;
        return anss;
}
matran po(matran X, ll n)
{
        matran res = X, ans = mot;
        while (n)
        {
                if (n % 2)
                        ans = prod(ans, res);
                res = prod(res, res);
                n /= 2;
        }
        return ans;
}
int main()
{
        ll x, n, m;
        cin >> x >> n >> m;
        cap init;
        init.u = 1;
        init.u_plus_1 = 1;
        matran M;
        M.a[0][0] = x;
        M.a[0][1] = 0;
        M.a[1][0] = 1;
        M.a[1][1] = 1;
        mot.a[0][0] = 1;
        mot.a[0][1] = 0;
        mot.a[1][0] = 0;
        mot.a[1][1] = 1;
        mod = m;
        matran res = po(M, n);
        cap ansss = prod1(init, res);

        cout << ansss.u << '\n';
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbGwgbG9uZyBsb25nCi8vICNkZWZpbmUgbW9kIDEwMDAwMDAwMDcKbGwgbW9kLCBtOwpzdHJ1Y3QgbWF0cmFuCnsKICAgICAgICBsbCBhWzJdWzJdOwogICAgICAgIHZvaWQgcHJpbnQoKQogICAgICAgIHsKICAgICAgICAgICAgICAgIGZvciAobGwgaSA9IDA7IGkgPCAyOyBpKyspCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIGZvciAobGwgaiA9IDA7IGogPCAyOyBqKyspCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY291dCA8PCBhW2ldW2pdIDw8ICIgIjsKICAgICAgICAgICAgICAgICAgICAgICAgY291dCA8PCAnXG4nOwogICAgICAgICAgICAgICAgfQogICAgICAgIH0KfTsKbWF0cmFuIG1vdDsKc3RydWN0IGNhcAp7CiAgICAgICAgbGwgdSwgdV9wbHVzXzE7CiAgICAgICAgdm9pZCBwcmludCgpCiAgICAgICAgewogICAgICAgICAgICAgICAgY291dCA8PCB1IDw8ICIgIiA8PCB1X3BsdXNfMSA8PCAnXG4nOwogICAgICAgIH0KfTsKbGwgZihsbCBhLCBsbCBuLCBsbCBtb2QpCnsKICAgICAgICBsbCByZXMgPSBhLCBhbnMgPSAwOwogICAgICAgIHdoaWxlIChuKQogICAgICAgIHsKICAgICAgICAgICAgICAgIGlmIChuICUgMikKICAgICAgICAgICAgICAgICAgICAgICAgYW5zID0gKGFucyArIHJlcykgJSBtb2Q7CiAgICAgICAgICAgICAgICByZXMgPSAocmVzICsgcmVzKSAlIG1vZDsKICAgICAgICAgICAgICAgIG4gLz0gMjsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIGFuczsKfQpsbCBwbyhsbCBhLCBsbCBuKQp7CiAgICAgICAgbGwgcmVzID0gYSwgYW5zID0gMTsKICAgICAgICB3aGlsZSAobikKICAgICAgICB7CiAgICAgICAgICAgICAgICBpZiAobiAlIDIpCiAgICAgICAgICAgICAgICAgICAgICAgIGFucyA9IGYoYW5zLCByZXMsIG1vZCk7CiAgICAgICAgICAgICAgICByZXMgPSBmKHJlcywgcmVzLCBtb2QpOwogICAgICAgICAgICAgICAgbiAvPSAyOwogICAgICAgIH0KICAgICAgICByZXR1cm4gYW5zOwp9CmxsIGFrYShsbCBwLCBsbCBhbHBoYSkKewogICAgICAgIGlmIChhbHBoYSA9PSAwKQogICAgICAgICAgICAgICAgcmV0dXJuIDE7CiAgICAgICAgaWYgKGFscGhhID09IDEpCiAgICAgICAgICAgICAgICByZXR1cm4gKHAgKyAxKSAlIG1vZDsKICAgICAgICBpZiAoYWxwaGEgJSAyID09IDEpCiAgICAgICAgICAgICAgICByZXR1cm4gKGYocCwgYWthKHAsIGFscGhhIC0gMSksIG1vZCkgKyAxKSAlIG1vZDsKICAgICAgICBpZiAoYWxwaGEgJSAyID09IDApCiAgICAgICAgICAgICAgICByZXR1cm4gKGYoKHBvKHAsIGFscGhhIC8gMikgKyAxKSwgKChha2EocCwgYWxwaGEgLyAyKSAtIDEgKyBtb2QpICUgbW9kKSwgbW9kKSArIDEpICUgbW9kOwp9CmNhcCBwcm9kMShjYXAgcHAsIG1hdHJhbiBYKQp7CiAgICAgICAgY2FwIGFuczsKICAgICAgICBhbnMudSA9IChmKHBwLnUsIFguYVswXVswXSwgbW9kKSArIGYocHAudV9wbHVzXzEsIFguYVsxXVswXSwgbW9kKSkgJSBtb2Q7CiAgICAgICAgYW5zLnVfcGx1c18xID0gKGYocHAudSwgWC5hWzFdWzBdLCBtb2QpICsgZihwcC51X3BsdXNfMSwgWC5hWzFdWzFdLCBtb2QpKSAlIG1vZDsKICAgICAgICByZXR1cm4gYW5zOwp9Cm1hdHJhbiBwcm9kKG1hdHJhbiBBLCBtYXRyYW4gQikKewogICAgICAgIG1hdHJhbiBhbnNzOwogICAgICAgIGFuc3MuYVswXVswXSA9IChmKEEuYVswXVswXSwgQi5hWzBdWzBdLCBtb2QpICsgZihBLmFbMF1bMV0sIEIuYVsxXVswXSwgbW9kKSkgJSBtb2Q7CiAgICAgICAgYW5zcy5hWzBdWzFdID0gKGYoQS5hWzBdWzBdLCBCLmFbMF1bMV0sIG1vZCkgKyBmKEEuYVswXVsxXSwgQi5hWzFdWzFdLCBtb2QpKSAlIG1vZDsKICAgICAgICBhbnNzLmFbMV1bMF0gPSAoZihBLmFbMV1bMF0sIEIuYVswXVswXSwgbW9kKSArIGYoQS5hWzFdWzFdLCBCLmFbMV1bMF0sIG1vZCkpICUgbW9kOwogICAgICAgIGFuc3MuYVsxXVsxXSA9IChmKEEuYVsxXVswXSwgQi5hWzBdWzFdLCBtb2QpICsgZihBLmFbMV1bMV0sIEIuYVsxXVsxXSwgbW9kKSkgJSBtb2Q7CiAgICAgICAgcmV0dXJuIGFuc3M7Cn0KbWF0cmFuIHBvKG1hdHJhbiBYLCBsbCBuKQp7CiAgICAgICAgbWF0cmFuIHJlcyA9IFgsIGFucyA9IG1vdDsKICAgICAgICB3aGlsZSAobikKICAgICAgICB7CiAgICAgICAgICAgICAgICBpZiAobiAlIDIpCiAgICAgICAgICAgICAgICAgICAgICAgIGFucyA9IHByb2QoYW5zLCByZXMpOwogICAgICAgICAgICAgICAgcmVzID0gcHJvZChyZXMsIHJlcyk7CiAgICAgICAgICAgICAgICBuIC89IDI7CiAgICAgICAgfQogICAgICAgIHJldHVybiBhbnM7Cn0KaW50IG1haW4oKQp7CiAgICAgICAgbGwgeCwgbiwgbTsKICAgICAgICBjaW4gPj4geCA+PiBuID4+IG07CiAgICAgICAgY2FwIGluaXQ7CiAgICAgICAgaW5pdC51ID0gMTsKICAgICAgICBpbml0LnVfcGx1c18xID0gMTsKICAgICAgICBtYXRyYW4gTTsKICAgICAgICBNLmFbMF1bMF0gPSB4OwogICAgICAgIE0uYVswXVsxXSA9IDA7CiAgICAgICAgTS5hWzFdWzBdID0gMTsKICAgICAgICBNLmFbMV1bMV0gPSAxOwogICAgICAgIG1vdC5hWzBdWzBdID0gMTsKICAgICAgICBtb3QuYVswXVsxXSA9IDA7CiAgICAgICAgbW90LmFbMV1bMF0gPSAwOwogICAgICAgIG1vdC5hWzFdWzFdID0gMTsKICAgICAgICBtb2QgPSBtOwogICAgICAgIG1hdHJhbiByZXMgPSBwbyhNLCBuKTsKICAgICAgICBjYXAgYW5zc3MgPSBwcm9kMShpbml0LCByZXMpOwoKICAgICAgICBjb3V0IDw8IGFuc3NzLnUgPDwgJ1xuJzsKfQ==

MiA2IDEwMDA=

2 6 1000