Faixas em negativo

Time limit: 2000 msMemory limit: 256 MB

Uma faixa circular tem $n$ posições, cada uma branca ou preta. Não há uma posição inicial marcada. Além disso, a faixa pode ser vista em negativo, trocando simultaneamente branco por preto e preto por branco em todas as posições.

Duas pinturas são equivalentes se é possível obter uma da outra por um deslocamento cíclico, possivelmente seguido dessa troca global de cores. A ordem das posições não pode ser invertida, e não é permitido trocar a cor de apenas algumas posições.

Formalmente, representando branco por $0$ e preto por $1$ , $X$ e $Y$ são equivalentes se existem $r\in\{0,\ldots,n-1\}$ e $b\in\{0,1\}$ tais que

$Y_i=X_{(i+r)\bmod n}\mathbin{\oplus}b$

para todo $i$ , onde $\oplus$ é o ou exclusivo. Qualquer quantidade de posições pretas é permitida, inclusive zero e $n$ .

Conte as pinturas diferentes e imprima a resposta módulo $M$ . O módulo é dado na entrada e não precisa ser primo.

Input

Uma linha com dois inteiros $n$ e $M$ .

$1\le n\le 10^9$ .
$1\le M\le 10^9$ .

Output

O resto da quantidade de classes de equivalência na divisão por $M$ , entre $0$ e $M-1$ .

Samples

Sample 1

Input

4 100

Output

Podemos escolher os representantes 0000, 0001, 0011 e 0101. Por exemplo, 1110 é equivalente a 0001 pela troca global de cores.

Sample 2

Input

4 2

Output

Sample 3

Input

1 17

Output

As duas pinturas de uma posição são equivalentes.