佳佳對數(shù)學，尤其對數(shù)列十分感興趣。在研究完 Fibonacci 數(shù)列后，他創(chuàng)造出許多稀奇古怪的數(shù)列。例如用 S(n) 表示 Fibonacci 前 n 項和 modm 的值，即 S(n)=(F₁+F₂+...+F_n)mod m，其中 F₁=F₂=1,F_i=F_i?1+F_i?2 ?？蛇@對佳佳來說還是小菜一碟。

終于，她找到了一個自己解決不了的問題。用 T(n)=(F₁+2F₂+3F₃+...+nF_n) mod m 表示 Fibonacci 數(shù)列前 n 項變形后的和 mod m 的值。

現(xiàn)在佳佳告訴你了一個 n 和 m，請求出 T(n) 的值。

輸入數(shù)據(jù)包括一行，兩個用空格隔開的整數(shù) n,m。

僅一行，T(n) 的值。

樣例解釋

T(5)=(1+2×1+3×2+4×3+5×5)mod 5=1
數(shù)據(jù)范圍與提示：

對于 30% 的數(shù)據(jù)，1≤n≤1000；

對于 60% 的數(shù)據(jù)，1≤m≤1000；

對于 100% 的數(shù)據(jù)，1≤n,m≤2³¹?1。

信息學一本通 數(shù)學