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

Entrada	Saída
0 100	1
1 100	1
2 100	3
3 100	5
10 10	7
3467 9350	7631