무한 문자열

컴퓨터 과학자들은 현재 비밀 코드를 실험하고 있으며, 그들이 사용할 무한한 길이의 문자열을 생성하는 방법을 개발했습니다.

문자열 s 가 주어지면, F(s)는 s와 오른쪽으로 한 문자씩 '회전'된 s로 이루어져 있습니다(오른쪽 회전에서는 s의 마지막 문자가 돌아다니며 새로운 첫 번째 문자가 됩니다). 초기 문자열 s가 주어지면, 컴퓨터 과학자들은 F를 반복 적용하여 무한한 길이의 코드 문자열을 만듭니다. 각 단계에서 현재 문자열의 길이는 두 배가 됩니다.

초기 문자열과 인덱스 N이 주어지면, 무한 코드 문자열 내의 N번째 문자를 계산하는데 컴퓨터 과학자들을 도와주세요.

입력은 문자열과 N을 포함하는 한 줄로 구성됩니다. 문자열은 최대 30개의 대문자로 구성되며, N ≤ 1018입니다.

N이 너무 커서 표준 32비트 정수에 맞지 않을 수 있으므로, 64비트 정수 유형(예: C/C++의 'long long')을 사용해야 할 수도 있습니다.

초기 문자열로 만든 무한 코드의 N번째 문자를 출력해주세요. 첫 번째 문자는 N=1입니다.