int n, m, A; longlong powA[N]; longlong ans; std::vector<int> border;
inlinelonglongcalc(int x, int y, __int128 S){ if (y < x - m + 1) { return powA[x - m - y]; } return (S >> (y - x + m)) & 1; }
inlinelonglongdp(__int128 S){ if (!(((__int128)1 << m) & S)) return0; if (S >> (m + 1)) return0; longlong ret = 0; std::vector<longlong> f(N); for (int i = m; i <= n; ++i) { f[i] = powA[i - m]; for (int j = m; j < i; ++j) f[i] = (f[i] + P - f[j] * calc(i, j, S) % P); f[i] %= P; ret = (ret + f[i] * powA[n - i]) % P; } return ret % P; }
std::vector<int> dfs(__int128 S, int ways){ ans = (ans + dp(S) * ways) % P; int last = border.back(); std::vector<int> ret(N); ret[last] = (ret[last] + ways) % P; for (int x = last + 1; x <= m; ++x) { border.push_back(x); int tmp = ways; for (int i = 0; i + 1 < border.size(); ++i) { int v = border[i]; if (v + v > x && !(S & ((__int128)1 << (v + v - x)))) goto next; } if (last + last < x) tmp = tmp * powA[x - last - last] % P; tmp = (tmp - ret[x] + P) % P; if (tmp) { std::vector<int> vec = dfs(S ((__int128)1 << x), tmp); for (int i = 0; i <= m; ++i) ret[i] = (ret[i] + vec[i]) % P; } next: border.pop_back(); } return ret; }
intmain(){ std::cin >> n >> m >> A; powA[0] = 1; for (int i = 1; i < N; ++i) powA[i] = powA[i - 1] * A % P; border.push_back(0); dfs(0, 1); std::cout << ans << std::endl; return0; }