25583번 - 첨탑 부수기

현기는 평소에 첨탑 부수기라는 게임을 즐겨한다. 첨탑 부수기 게임은 1층에 존재하는 첨탑의 입구로 들어가 꼭대기 층까지 한 층씩 등반하며 첨탑 내의 모든 괴물을 쓰러뜨리는 게임이다. 첨탑의 꼭대기까지 등반하여 게임을 클리어하더라도 다시 도전하면 그때마다 또 다른 괴물을 만날 수 있어 몇 번을 하더라도 새로운 재미를 선사한다.

첨탑 부수기 게임은 새로운 게임을 시작할 때 무작위로 생성되는 시드$(=Seed)$를 바탕으로 각 층에 생성되는 괴물의 강함$(=Strength)$이 정해진다. 시드는 알파벳 대소문자와 0을 제외한 숫자로 이루어진 10자리 문자열이다. 괴물의 강함을 계산하기 위해 시드의 각 자리 문자를 사용할 때에는 아래의 표와 같이 다른 정숫값으로 바꿔 연산한다.

예를 들어 시드가 "AB1z8DcdT4"일 경우에 시드의 첫 번째 문자$(=Seed[0])$인 'A'는 정수 10을 의미한다. 여기서, $Seed[i]$는 시드를 구성하는 문자 중 왼쪽에서 $i+1$번째 문자에 해당한다.

층 수가 $N$인 첨탑 부수기 게임을 플레이할 때, 1층에서 마주치는 괴물의 강함은 1이고 $k(\neq 1)$층에서 마주치는 괴물의 강함은 아래와 같이 계산한다.

$\begin{cases} f(i,k) = Seed[(i\times k)\ \textrm{mod}\ 10] \\ g(k) = \sum_{i=1}^{10} f(i,k) \times k \\ Strength(k) = g(k) ^ {Strength(k-1)} \end{cases}$

현기가 꼭대기 층이 $N$층인 첨탑 부수기 게임을 새로 시작할 때, 꼭대기 층에서 마주치는 괴물의 강함을 구하여라. 단, 괴물의 강함이 매우 클 수 있으므로 괴물의 강함을 $M$으로 나눈 나머지를 출력하라.

첫째 줄에 두 정수 $N$과 $M$이 주어진다. $(1\le N, M \le10^9)$

둘째 줄에 $Seed$가 주어진다. $Seed$는 알파벳 대소문자와 0을 제외한 숫자로 이루어진 10자리 문자열이다.

첫째 줄에 괴물의 강함을 $M$으로 나눈 나머지를 출력한다.