#include "pilgrimage.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 3000 + 5;
int mod;
int f[maxn][maxn << 1], Answer[maxn], Inv2, Inv4;
inline int Ksm(int x, int y) {
    int res = 1;
    while(y) {
        if(y & 1) res = 1ll * res * x % mod;
        x = 1ll * x * x % mod;
    }
    return res;
}
inline int Calc(int x) { return Ksm(x, mod - 2); }
inline int ask(ll n) { return Answer[n]; }
inline void init(int o, int p) {
    mod = p;
    f[0][3000] = 1, Inv2 = Calc(2), Inv4 = Calc(4);
    for(register int i = 1; i <= 3000; ++i)
        for(register int j = 3000 - i; j <= 3000 + i; ++j)
            f[i][j] = (1ll * f[i - 1][j - 1] * Inv4 % mod + 1ll * f[i - 1][j] * Inv2 % mod + 1ll * f[i - 1][j + 1] * Inv4 % mod) % mod;
    for(register int i = 1; i <= 3000; ++i) {
        for(register int j = 3000 - i; j <= 3000 + i; ++j) Answer[i] = (1ll * Answer[i] + 1ll * f[i][i - j] * abs(j - 3000) % mod) % mod;
    }
}

/usr/bin/ld: /tmp/ccMzgtz6.o: in function `main':
implementer.cpp:(.text.startup+0x2b): undefined reference to `init(int, int)'
/usr/bin/ld: implementer.cpp:(.text.startup+0x16c): undefined reference to `ask(long long)'
collect2: error: ld returned 1 exit status