Quantas chamadas recursivas

Os números de fibonacci são definidos pela seguinte recorrência:

• $$fib(0) = 0$$
• $$fib(1) = 1$$
• $$fib(n) = fib(n-1) + fib(n-2)$$

Mas não estamos interessados em números de Fibonacci aqui. Gostaríamos de saber quantas chamadas recursivas seriam necessárias para um determinado número de Fibonacci $$n$$, seguindo a recorrência normal. Uma vez que os números serão bem grandes, não será uma tarefa muito simples para você. Mas então vamos torná-la um pouco mais fácil: queremos que você apresente somente o resto desse número módulo $$b$$.

Entrada

A entrada consiste de dois números inteiros $$n\ (0 \leq n \leq 10^{18})$$ e $$b\ (1 \leq b \leq 10^4)$$

Saída

Você deverá imprimir somente um número $$x$$ – o número de chamadas recursivas para calcular $$fib(n)$$ módulo $$b$$.

Exemplos