Flavia acum vrea să rezolve două cerinţe:
# Dându-se un şir $S$ interesant de lungime $N$, să se găsească al câtelea este el, în ordine lexicografică, printre toate şirurile interesante de lungime $N$, modulo $10^9^+7$

# Dându-se un număr $N$ şi un număr $K$ să se găseasca al $K$-lea şir interesant de lungime $N$ în ordine lexicografică. O puteţi ajuta?

# Dându-se un număr $N$ şi un număr $K$ să se găseasca al $K$-lea şir interesant de lungime $N$ în ordine lexicografică.
 
O puteţi ajuta?

h2. Date de intrare

h2. Restricţii

* Pentru teste in valoare de $20$ de puncte, $P=1$ şi $N ≤ 20$
* Pentru teste in valoare de $30$ de puncte, $P=1$ şi $N ≤ 1 000 000$
* Pentru teste in valoare de $20$ de puncte, $P=2$. $N ≤ 100$ şi $K ≤ 1 000 000$
* Pentru teste in valoare de $30$ de puncte, $P=2$. $N ≤ 1 000 000$ şi $K ≤ 1 000 000 000$

* Pentru teste în valoare de $20$ de puncte, $P=1$ şi $N ≤ 20$
* Pentru alte teste în valoare de $30$ de puncte, $P=1$ şi $N ≤ 1 000 000$
* Pentru alte teste în valoare de $20$ de puncte, $P=2$, $N ≤ 100$ şi $K ≤ 1 000 000$
* Pentru alte teste în valoare de $30$ de puncte, $P=2$, $N ≤ 1 000 000$ şi $K ≤ 1 000 000 000$

h2. Exemplu