Hashing

If you have taken a data structures course, you have heard of hash functions. A hash function takes an input of arbitrary length and returns an output of fixed length, and it is widely used for storing and searching data.

In this problem you will learn one hash function for strings that will stay useful. Assume the input string consists only of lowercase English letters (a, b, ..., z). There are 26 letters in total, so each letter can be given a unique number: $a = 1$, $b = 2$, $c = 3$, and so on up to $z = 26$. A string can then be rewritten as a sequence of numbers. The string "abba" becomes the sequence $1, 2, 2, 1$.

To compute a hash value, we turn such a string, that is, such a sequence, into a single integer. The simplest way is to add up all the values of the sequence. Since a hash function must have outputs within a finite range, take the remainder modulo a suitably large number $M$. In symbols:

$H = \sum_{i=0}^{l-1}{a_i} \mod M$

There are infinitely many possible input strings, but the output range is fixed. By the pigeonhole principle, different strings can share the same hash value. This is called a hash collision, and a good hash function causes as few collisions as possible. The function defined above is a bad hash function because just reordering the letters causes a collision. So let us improve it.

How can the output change when the order changes? Give each term of the sequence its own coefficient. The standard approach is to multiply the term at each position by a fixed number raised to the power of its index, then add the results:

$H = \sum_{i=0}^{l-1}{a_ir^i} \mod M$

It is customary to choose $r$ and $M$ coprime to each other. Here $r$ is 31, a prime larger than 26, and $M$ is 1234567891, which is also prime.

Your task is to compute the hash value of the given string with this formula. It looks simple, but it is used often, so remember it and put it to good use.

The first line contains the length $L$ of the string. The second line contains the string, which consists only of lowercase English letters and has length $L$.

Print, as an integer on one line, the hash value computed from the given string with the hash function from the statement.

Computing each power from scratch makes the numbers huge, so update the powers of $r$ one step at a time while taking the remainder modulo $M$ at every step. That is, set $p_0 = 1$ and $p_{i+1} = (p_i \times r) \mod M$, and accumulate $H = (H + a_i \times p_i) \mod M$. Note that $r^0 = 1$.