prefix-hash

import java.util.StringTokenizer

class PrefixHash(
    private val string: String,
    private val base: Int,
    private val modulus: Int
) {
    private val powers: LongArray
    private val hashes: LongArray

    init {
        powers = initPowers()
        hashes = initHashes()
    }

    /**
     * 1 <= [start] <= [end] <= [string.length]
     *
     * @param start inclusive
     * @param end inclusive
     */
    fun getSubstringHash(start: Int, end: Int): Long {
        return (hashes[end] - hashes[start - 1]) * powers[string.length - start] % modulus
    }

    private fun initPowers() : LongArray {
        // power to (base ^ power) % modulus
        val p = LongArray(string.length + 1)
        p[0] = 1
        for (i in 1..string.length) {
            p[i] = (p[i - 1] * base) % modulus
        }
        return p
    }

    private fun initHashes(): LongArray {
        val h = LongArray(string.length + 1)
        h[0] = 0L
        for (i in 1..string.length) {
            h[i] = (h[i - 1] * base + string[i - 1].code) % modulus
        }
        return h
    }
}

fun main() {
    val reader = System.`in`.bufferedReader()
    val writer = System.out.bufferedWriter()

    val base = reader.readLine().toInt()
    val modulus = reader.readLine().toInt()
    val string = reader.readLine()
    val count = reader.readLine().toInt()

    val substringIndexes = Array(count) {
        val tokenizer = StringTokenizer(reader.readLine())
        Pair(tokenizer.nextToken().toInt(), tokenizer.nextToken().toInt())
    }
    val stringHashContainer = PrefixHash(string, base, modulus)

    with(writer) {
        substringIndexes
            .forEach {
                val substringHash = stringHashContainer.getSubstringHash(it.first, it.second)
                write(substringHash.toString())
                newLine()
            }
        flush()
    }
}