U204311 白的Fibonacci

白是一位擅长思考的女孩子。 由于某位乐于助人的大臣替他们包揽了一切的常务，白最近无所事事。于是她闲的没事干翻空的手机。她在翻找手机时（空为啥要放这种东西）找到了这么一种神奇的数列： $定义 F_{n} 为Fibonacci数列的第n项，有F_{n} = F_{n-1} + F_{n-2} 。特殊的，我们有F_{0} = F_{1} = 1 。$ 顺便删掉了一系列非妹控系的本子。 白也是一个争强好胜的女孩子。（确实 她想了想，觉得这可以在她与空那$500000:500000:1000000$的竞赛中增加一次她的胜利，于是在$10^{-100}s$内想出了一个简单的级数，并在$10^{-25}s$内凭空创造了线性代数，在$10^{-50}s$内使用矩阵想出了它的任意值求解方式。这个级数具体定义如下： $ F_{n} 定义如上，为Fibonacci数列的第n项，有S_{n} = \sum\limits_{i=0}^{n} 2^iF_i。给定n，求得S_{n}。$ 很显然，空并不是很擅长口算级数，因此他想到，手机里还有GCC编译器（所以说为啥会有这种东西）可以帮助他（以及为啥他会认为这种东西有用）。 于是，他用$5min$通过手扒编译器的方式学完了C++，并充分发挥自身才能，用$5s$求他的妹妹给他想个简单的解法，用$2min$学会了矩阵快速幂，并用$1s$打出了代码。代码在$10^{-102}s$内（休比的威能）输出了正确的结果，成功地粉碎了妹妹的阴谋。（不 人类种首都的王宫里，今天又是无事发生的一天呢。

你听到了他们间的比试，自己也想试试。 然而，你的机子没有「 」的加持，无法算得超过$9223372036854775807$的值，因此你的得数需要对$M$取模。 为了证明你比空的$1/10^{100}$强，你的代码需要在$0.01s$内得到结果。

唯一一行。第一行有两个实数，分别为$n,m$。 $10^2 < N < 10^{18}$， $M < 10^{9}。$

唯一一行。第一行唯一一个数表示$S_{n} \space \operatorname{mod} m$的值。