시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 256 MB222100.000%

문제

The school organizes a fair to commemorate Fibonaccis. Johnny is responsible for a gift shop, in which you can pay only using special vouchers, whose face values are Fibonacci numbers. Johnny has difficulty with processing such strange values and has decided to accept only exact payments with exactly $k$ vouchers, not necessarily of different face values. Now he needs to set the prices -- there are $n$ different items at the gift shop and Johhny wants to put a different price on each of them. Sometimes there are many ways to pay one price, in such a case Johnny counts this price only once. He calculated all the prices and now he wants to verify his calculations. To make it quick, it is enough to name the last, $n$-th price. Help Johnny -- write a program that, given $n$ and $k$, computes the $n$-th smallest price that can be paid using exactly $k$ vouchers.

입력

The first and only line of the input contains two integers $k$ and $n$ ($1\leq k \leq 100, 1 \leq n \leq 10^{18}$), separated by a single space.

출력

You should write a single integer in the first and only line of the output -- the $n$-th smallest number that can be paid with $k$ (not necessarily different) vouchers whose face values are Fibonacci numbers, assuming that this number is at most $10^{18}$, or "NIE" (Polish for "no"), if it is larger than $10^{18}$.

예제 입력 1

2 11

예제 출력 1

13

예제 입력 2

1 100

예제 출력 2

NIE

노트

In Sample 1, using exactly $2$ vouchers it is not possible to pay the prices $1$ and $12$.

In Sample 2, the 100-th Fibonacci number is (much) greater than $10^{18}$.