#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll MOD = 1'000'000'000'000'000'000 + 31;

ll power(ll a, ll b) {
    ll ans = 1;
    for(;b;b>>=1) {
        if(b&1) ans=(__int128)ans*a%MOD;
        a=(__int128)a*a%MOD;
    }
    return ans;
}

void solve() {
    int n; cin >> n;
    ll ans = 300;
    while (n < 1000000) {
        ans = power(42, ans);
        n++;
    }
    cout << ans << '\n';
}

signed main() {
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int T = 1;
    // cin >> T;
    while (T--) solve();
}