#include <bits/stdc++.h>
using namespace std;

#define sz(o) ((int)o.size())
#define all(o) o.begin(), o.end()
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define repr(i, a, b) for(int i = (a); i >= (b); i--)
#define INF 1000000000000000000LL
#define MOD 1000000007
#define EPS 1e-9
#define PI 3.1415926535
#define ff first
#define ss second
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<pi> vpi;

class SimpleMathProblem{
public:

    map<int, int> factorize(int n){
        map<int, int> res;
        for(ll i = 2; i * i <= n; i++){
            while(n % i == 0){
                res[i]++;
                n /= i;
            }
        }
        if(n > 1) res[n]++;
        return res;
    }

    int phi(int n){
        map<int, int> factors = factorize(n);
        int res = n;
        for(auto p : factors){
            res *= (p.ff - 1);
            res /= p.ff;
        }
        return res;
    }

    int bpow(int a, int b, int m){
        int res = 1;
        while(b > 0){
            if(b & 1) res = (int)((res * 1LL * a) % m);
            a = (int)((a * 1LL * a) % m);
            b >>= 1;
        }
        return res;
    }


    int calculate(int a, int b, int c, int m){
        map<int, int> factors = factorize(m);
        int ans = 0;
        vector<pair<int, pi>> v;
        for(auto p : factors){
            int mod = (int)pow(p.ff, p.ss);
            if(a % p.ff != 0){
                int x = bpow(b, c, phi(mod));
                int ci = bpow(a, x, mod);
                int N = m / mod;
                int invN = bpow(N, mod-2, mod);
                v.push_back({ci, {N, invN}});
            }
        }
        for(auto p : v){
            ans += (int)((((p.ff * 1LL * p.ss.ff) % m) * 1LL * p.ss.ss) % m);
            ans %= m;
        }
        return ans;
    }
};

void solve(int testcase){
    SimpleMathProblem *obj = new SimpleMathProblem();
    cout << obj->calculate(3737373, 7373737, 37373, 737373737);
}

int main() {
    #ifdef VPAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout << fixed << setprecision(20);
    clock_t b = clock();
    int t = 1;
    //cin >> t;
    rep(tt, 1, t) solve(tt);
    clock_t e = clock();
    cerr << (double(e - b) / CLOCKS_PER_SEC) << " sec";
    return 0;
}