structMatrix { std::vector<std::vector<int>> a; Matrix() : a(k, std::vector<int>(k)) {} auto& operator [](int x) { return a[x]; } Matrix operator *(Matrix b) const { Matrix res; for (int i = 0; i < k; ++ i) for (int j = 0; j < k; ++ j) for (int l = 0; l < k; ++ l) res[i][l] = (res[i][l] + (LL) a[i][j] * b[j][l]) % Mod; return res; } };
Matrix qpow(Matrix a, LL d) { Matrix res; for (int i = 0; i < k; ++ i) res[i][i] = 1; for (; d; d >>= 1, a = a * a) if (d & 1) res = res * a; return res; }
intmain() { std::cin >> n >> Mod >> k >> r, n *= k; Matrix trs; for (int i = 0; i < k; ++ i) trs[i][(i + 1) % k] ++, trs[i][i] ++; trs = qpow(trs, n); std::cout << trs[0][r] << '\n'; return0; }