Hide

Problem J
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:

\begin{align*} s_1 & = \texttt{N} \\ s_2 & = \texttt{A} \\ s_ n & = s_{n-2} + s_{n-1} \end{align*}

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

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

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

Please log in to submit a solution to this problem

Log in