첨탑 부수기

현기는 평소에 첨탑 부수기라는 게임을 즐겨 한다. 이 게임은 1층 입구로 들어가 꼭대기 층까지 한 층씩 올라가며, 각 층의 괴물을 모두 쓰러뜨리는 게임이다. 꼭대기까지 클리어한 뒤에 다시 도전하면 매번 다른 괴물을 만난다.

새 게임을 시작할 때마다 무작위로 시드(Seed)가 생성되고, 시드에 따라 각 층 괴물의 강함(Strength)이 정해진다. 시드는 알파벳 대소문자와 0을 제외한 숫자로 이루어진 10자리 문자열이다. 강함을 계산할 때 시드의 각 문자는 아래 표의 정숫값으로 바꾸어 사용한다.

예를 들어 시드가 AB1z8DcdT4일 때, 첫 번째 문자 'A'는 정수 10을 의미한다. $Seed[i]$는 왼쪽에서 $i+1$번째 문자이다.

1층 괴물의 강함은 1이다. $k \neq 1$층 괴물의 강함은 다음과 같이 계산한다.

$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)}$

꼭대기 층이 $N$층인 첨탑 부수기 게임에서, 꼭대기 층 괴물의 강함을 $M$으로 나눈 나머지를 구하시오.

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

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

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