c_prefix_hash.py

"""
C. Префиксные хеши

Алла не остановилась на достигнутом –— теперь она хочет научиться
быстро вычислять хеши произвольных подстрок данной строки. Помогите ей!

На вход поступают запросы на подсчёт хешей разных подстрок. Ответ на
каждый запрос должен выполняться за O(1). Допустимо в начале работы
программы сделать предподсчёт для дальнейшей работы со строкой.

Напомним, что полиномиальный хеш считается по формуле

В данной задаче необходимо использовать в качестве значений отдельных
символов их коды в таблице ASCII.

Формат ввода
В первой строке дано число a (1 ≤ a ≤ 1000) –— основание, по которому
считается хеш. Во второй строке дано число m (1 ≤ m ≤ 107) –— модуль.
В третьей строке дана строка s (0 ≤ |s| ≤ 106), состоящая из больших
и маленьких латинских букв.

В четвертой строке дано число запросов t –— натуральное число от 1 до 105.
В каждой из следующих t строк записаны через пробел два числа l и r –—
индексы начала и конца очередной подстроки. (1 ≤ l ≤ r ≤ |s|).

Формат вывода
Для каждого запроса выведите на отдельной строке хеш заданной в запросе
подстроки.

Пример 1
Ввод
1000
1000009
abcdefgh
7
1 1
1 5
2 3
3 4
4 4
1 8
5 8

Вывод
97
225076
98099
99100
100
436420
193195
"""


def hashes_arr(b):
    s_len = len(b) + 1
    hashes = [0] * s_len
    hashes[1] = b[0]
    for i in range(2, s_len):
        hashes[i] = (hashes[i-1] * a + b[i-1]) % m
    return hashes


def fast_pow(x, p, r):
    m = x % r
    t = 1
    while p:
        if p % 2:
            t *= m
            t %= r
        m *= m
        m %= r
        p //= 2
    return t % r


if __name__ == '__main__':
    a = int(input().strip())
    m = int(input().strip())
    hashes = hashes_arr(bytes(input().strip(), encoding='ascii'))
    n = int(input().strip())

    res = [0]*n
    for i in range(n):
        s, e = input().strip().split()
        start, end = int(s), int(e)
        res[i] = (
            hashes[end] % m - hashes[start-1] * fast_pow(a, end - start + 1, m)
        ) % m
    print(*res, sep='\n')