Batmanacci

The Fibonacci sequence can be defined as follows:

\begin{align*} \mathrm{fib}_1 & = 1 \\ \mathrm{fib}_2 & = 1 \\ \mathrm{fib}_ n & = \mathrm{fib}_{n-2} + \mathrm{fib}_{n-1} \end{align*}We get the sequence $1, 1, 2, 3, 5, 8, 13, 21, \ldots $. But there are many generalizations of the Fibonacci sequence. One of them is to start with other numbers, like:

\begin{align*} f_1 & = 5 \\ f_2 & = 4 \\ f_ n & = f_{n-2} + f_{n-1} \end{align*}And we get the sequence $5, 4,
9, 13, 22, 35, 57, \ldots $. But what if we start with
something other than numbers? Let us define the
*Batmanacci* sequence in the following
manner:

where $+$ is string
concatenation. Now we get the sequence `N`, `A`, `NA`, `ANA`, `NAANA`, ….

Given $N$ and $K$, what is the $K$-th letter in the $N$-th string in the Batmanacci sequence?

Input consists of a single line containing two integers $N$ ($1 \leq N \leq 10^5$) and $K$ ($1 \leq K \leq 10^{18}$). It is guaranteed that $K$ is at most the length of the $N$-th string in the Batmanacci sequence.

Output the $K$-th letter in the $N$-th string in the Batmanacci sequence.

Sample Input 1 | Sample Output 1 |
---|---|

7 7 |
N |

Sample Input 2 | Sample Output 2 |
---|---|

777 777 |
A |