#include <cstring>

constexpr int hashi(const char *s, int p, int mod, int index) {
    return index == std::strlen(s) ? 1 : index + 1 == std::strlen(s) ? s[std::strlen(s) - 1] : (p * hashi(s, p, mod, index + 1) % mod);
}

constexpr int hash(const char *s, int p, int mod, int index = 0) {
    return hashi(s, p, mod, 0);
}