첨탑 부수기

문제

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

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


$Seed$ 의 각 자리 문자	1	$\cdots$	8	9	A	B	$\cdots$	Y	Z	a	b	$\cdots$	y	z
값	1	$\cdots$	8	9	10	11	$\cdots$	34	35	36	37	$\cdots$	60	61

예를 들어 시드가 "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$ 으로 나눈 나머지를 출력한다.