beecrowd | 1531

Fibonacci de Novo!

Por Gabriel Dalalio, ITA BR Brazil

Timelimit: 3

A famosa sequência de Fibonacci pode ser definida da seguinte maneira:

Sua tarefa é simples, calcular o valor do resto de Fib( Fib( N ) ) por M.

Entrada

A entrada é composta por vários casos de teste e termina com EOF. Cada caso de teste consiste de uma linha com dois inteiros N e M (1 ≤ N ≤ 109, 2 ≤ M ≤ 106).

Saída

Para cada caso de teste, imprima uma linha contendo um inteiro igual ao resto de Fib( Fib( N ) ) por M.

Exemplo de Entrada Exemplo de Saída

1 100
2 100
3 100
4 100
5 100
5 2
6 100

1
1
1
2
5
1
21