c083. $C.$數列上樓梯 - TCFSH CIRC Judge

Content

電電在爬樓梯時喜歡一次走很多階，而每次跨的階數都有限制，並且他喜歡算總共有幾種走法，他每次跨的階數只能是一個數列的值，數列規則如下：

$ A_0 = 1 $

$ A_1 = 1 $

$ A_n = A_{n-1} + A_{n-2} + 1 , (n\ge2) $

而在共有 $ x $ 階樓梯的情況下，電電每次可跨從 $ A_1 $ 到 $ A_n $ 中任一個階數，請幫他算一下他一共有幾種走法可以剛好走完？

Input

第一行有三個數字

第一個數字 $ n，0 \lt n \le 30 $

第二個數字 $ x，0 \lt x \le 10000 $

第三個數字 $ d，0 \lt d \lt 2^{64} $

Output

輸出恰好走完 $ x $ 階樓梯之走法數除以 $ d $ 的餘數

Sample Input #1

2 6 5

Sample Output #1

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (10%): 0.1s , <1K
公開測資點#1 (10%): 0.1s , <1K
公開測資點#2 (10%): 0.1s , <1K
公開測資點#3 (10%): 0.1s , <1K
公開測資點#4 (10%): 0.1s , <1K
公開測資點#5 (10%): 0.1s , <1K
公開測資點#6 (10%): 0.1s , <1K
公開測資點#7 (10%): 0.1s , <1K
公開測資點#8 (10%): 0.1s , <1K
公開測資點#9 (10%): 0.1s , <1K

Hint ：

Tags:

出處:

[管理者：

TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」