Problem C
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 |
