package sprint4.tasks.C

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.pow

fun String.polynomialHashToArray(a: Int, m: Int): LongArray {
    val result = LongArray(length)
    var res = 0L
    for (i in 0..lastIndex) {
        res = (res * a % m + this[i].code) % m
        result[i] = res
    }

    return result
}

fun LongArray.calcSubStringHash(left: Int, right: Int, a: Int, m: Int): Long {
    val rightHash = this[right]
    val leftMinusOneHash = if (left == 0) 0 else this[left - 1]
    val aPow = a.pow5(right - left + 1, m) % m
    return ((rightHash - (leftMinusOneHash * aPow) % m + m) % m)
}

//ИЗначально использовался этот метод, но выходит за рамки дабла Оо
fun Int.pow(pow: Int, m: Int) = (toDouble().pow(pow) % m).toLong()

//работает корректно, но долго
fun Int.pow2(pow: Int, m: Int): Long {
    var res = 1L
    for (i in 1..pow) res = res * this % m
    return res
}

//тоже работает, но тоже долго
fun Int.pow3(pow: Int, m: Int) = (toBigInteger().pow(pow).divideAndRemainder(m.toBigInteger())[1]).toLong()

//это тоже ожидаемо долго
fun Int.pow4(pow: Int, m: Int): Long {
    if (pow <= 120) return (toDouble().pow(pow) % m).toLong()
    return (pow4(pow / 2, m) * pow4(pow - pow / 2, m)) % m
}

//корректно и в пределах TL
fun Int.pow5(pow: Int, m: Int) = (toBigInteger().modPow(pow.toBigInteger(), m.toBigInteger())).toLong()

fun StringTokenizer.nextInt() = nextToken().toInt()

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val a = reader.readLine().toInt()
    val m = reader.readLine().toInt()
    val str = reader.readLine()
    val prefixHashes = str.polynomialHashToArray(a, m)
    val sb = StringBuilder()
    repeat(reader.readLine().toInt()) {
        val tokenizer = StringTokenizer(reader.readLine())
        val left = tokenizer.nextInt() - 1
        val right = tokenizer.nextInt() - 1

        val curResult = prefixHashes.calcSubStringHash(left, right, a, m)
        sb.appendLine(curResult)
    }
    println(sb)
}