Secret Cow Code

The cows are experimenting with secret codes, and have devised a method for creating an infinite-length string to be used as part of one of their codes.

Given a string $s$, let $F(s)$ be $s$ followed by $s$ "rotated" one character to the right. In a right rotation, the last character of $s$ moves around to become the new first character. Starting from an initial string $s$, the cows build their infinite-length code string by repeatedly applying $F$, so each step doubles the length of the current string.

Given the initial string and an index $N$, compute the character at the $N$-th position of the infinite code string.

The input is a single line containing a string followed by $N$, separated by a space. The string consists of at most 30 uppercase letters, and $N \le 10^{18}$.

$N$ may not fit in a standard 32-bit integer, so you may want to use a 64-bit integer type (for example, long long in C/C++).

Print the $N$-th character of the infinite code built from the initial string. The first character is at $N=1$.

In the sample, the initial string COW expands as follows:

COW -> COWWCO -> COWWCOOCOWWC
                 12345678