Алле очень понравился алгоритм вычисления полиномиального хеша. Помогите ей написать функцию, вычисляющую хеш строки s. В данной задаче необходимо использовать в качестве значений отдельных символов их коды в таблице ASCII.
Полиномиальный хеш считается по формуле:
В первой строке дано число a (1 ≤ a ≤ 1000) –— основание, по которому считается хеш.
Во второй строке дано число m (1 ≤ m ≤ 109) –— модуль.
В третьей строке дана строка s (0 ≤ |s| ≤ 106), состоящая из больших и маленьких латинских букв.
Выведите целое неотрицательное число –— хеш заданной строки.
|
123 100003 a |
97 |
|
123 100003 hash |
6080 |
|
123 100003 HaSH |
6080 |