Destroying the spire

Hyeongi often plays a game called Destroying the Spire. The player enters the spire at floor 1 and climbs one floor at a time to the top, defeating every monster on each floor. After clearing the spire, a new attempt brings different monsters.

When a new game starts, a seed (Seed) is generated at random. The seed determines the strength (Strength) of the monsters on each floor. The seed is a 10-character string made of letters A to Z, a to z, and digits 1 to 9 (0 is not used). To compute strength, each character of the seed is replaced with the integer value in the table below.

For example, when the seed is AB1z8DcdT4, the first character 'A' has the value 10. $Seed[i]$ is the character at position $i+1$ counting from the left.

The monster strength on floor 1 is 1. For floor $k \neq 1$, the strength is computed as follows.

$f(i,k) = Seed[(i \times k) \bmod 10]$

$g(k) = \sum_{i=1}^{10} f(i,k) \times k$

$Strength(k) = g(k)^{Strength(k-1)}$

Find the strength of the monster on the top floor, floor $N$, of a spire game with $N$ floors, modulo $M$.

The first line contains two integers $N$ and $M$. ($1 \le N, M \le 10^9$)

The second line contains $Seed$. $Seed$ is a 10-character string made of letters A to Z, a to z, and digits 1 to 9.

Print the strength of the monster on floor $N$ modulo $M$ on the first line.