#include <iostream>
using namespace std;
int main(void) {
    int M;
    cin >> M;
    long long cur = 4068289 % M;
    for (int i = 1; i < 2017; i++){
        long long f = cur * 4068289;
        cur = f % M;
    }
    int answer =  (cur + 2017) % M;
    cout << answer << endl;
}