비밀 소 암호

소들이 비밀 암호를 실험하고 있다. 소들은 암호의 일부로 쓸 무한히 긴 문자열을 만드는 방법을 고안했다.

문자열 $s$에 대해 $F(s)$는 $s$ 뒤에 $s$를 오른쪽으로 한 칸 "회전"한 문자열을 이어 붙인 것이다. 오른쪽 회전에서는 $s$의 마지막 문자가 맨 앞으로 옮겨 가 새로운 첫 문자가 된다. 소들은 처음 문자열 $s$에 $F$를 계속 적용해서 무한히 긴 암호 문자열을 만든다. 따라서 한 번 적용할 때마다 현재 문자열의 길이가 두 배가 된다.

처음 문자열과 위치 $N$이 주어질 때, 무한 암호 문자열의 $N$번째 문자를 구하는 프로그램을 작성하시오.

첫째 줄에 문자열과 $N$이 공백으로 구분되어 주어진다. 문자열은 알파벳 대문자로만 이루어져 있고 길이는 최대 30이다. $N \le 10^{18}$이다.

$N$은 32비트 정수 범위를 넘을 수 있으므로 64비트 정수 자료형(C/C++의 long long 등)을 사용하는 것이 좋다.

처음 문자열로 만든 무한 암호 문자열의 $N$번째 문자를 출력한다. 첫 문자는 $N=1$이다.

예제에서 처음 문자열 COW는 다음과 같이 늘어난다.

COW -> COWWCO -> COWWCOOCOWWC
                 12345678