package sprint4.tasks.A

fun main() {
    val a = readln().toInt()
    val m = readln().toInt()
    readln().polynomialHash(a, m).let(::println)
}

fun String.polynomialHash(a: Int, m: Int): Int {
    // можно воспользоваться свойствами остатка от деления:
    // (a+b)%c = (a%c + b%c)%c
    // (a*b)%c = ((a%c) * (b%c))%c
    // по первому свойству можно сумму разложить на сумму остатков
    // каждое слагаемое -- произведение, тоже можно разложить
    // второй множитель -- это степень а
    // (a*a)%n = ((a%n)*(a%n))%n
    // то есть хранить a в изначальном виде не нужно, можно хранить a%n
    val a = a % m
    // сумма изначально пустая
    var res = 0
    // т.к. в цикле идём задом наперёд, то и степень начинается с нулевой
    var pow = 1

    // в цикле перебираем строку от последнего символа до первого
    for (i in lastIndex downTo 0) {
        // пользуясь разложением остатка от суммы, раскладываем:
        // res -- накопленный итог как остаток от деления
        // ((this[i].code % m) * pow) % m -- второе слагаемое
        // состоит из this[i].code % m, умноженного на степень
        // но степень уже с взятым остатком, поэтому его ещё раз не считаем
        // и в конце берём остаток от деления второго слагаемого
        // а потом и всей суммы и записываем в накопленный итог
        res = (res + ((this[i].code % m) * pow) % m) % m
        // после того как произвели вычисления, надо увеличить степень
        // и pow, и a -- остатки от деления, поэтому их самих не делим, только их произведение
        pow = (pow * a) % m
    }
    // res хранит в себе накопленный итог
    return res
}