题目描述

佳佳对数学，尤其对数列十分感兴趣。

在研究完 Fibonacci数列后，他创造出许多稀奇古怪的数列。

例如用 $S(n)$表示 Fibonacci前$n$项和 $mod m$的值,即 $S(n)=(F_1+F_2+...+F_n)mod m$，其中$F_1=1,F_2=1,f_i=F_{i-1}+F_{i-2}$.

可这对佳佳来说还是小菜一碟。

终于，她找到了一个自己解决不了的问题。

用$T(n)=( F_1+2F_2, +3F_3+...+nF_n,)mod m$表示Fibonacci数列前$n$项变形后的和 $mod m$ 的值。

现在佳佳告诉你了一个 $n$ 和 $m$，请求出 $T(n)$的值。

输入

共一行，包含两个整数 $n$和 $m$。

输出

共一行，输出 $T(n)$的值。

5 5

1

样例解释

$T(5)=(1+2×1+3×2+4×3+5×5)mod5=1$

$1 \leq n,m \leq 2^{31}-1$