電電在爬樓梯時喜歡一次走很多階，而每次跨的階數都有限制，並且他喜歡算總共有幾種走法，他每次跨的階數只能是一個數列的值，數列規則如下：
\( A_0 = 1 \)
\( A_1 = 1 \)
\( A_n = A_{n-1} + A_{n-2} + 1 , (n\ge2) \)
而在共有 \( x \) 階樓梯的情況下，電電每次可跨從 \( A_1 \) 到 \( A_n \) 中任一個階數，請幫他算一下他一共有幾種走法可以剛好走完？

輸入格式

第一行有三個數字 第一個數字 \( n，0 \lt n \le 30 \) 第二個數字 \( x，0 \lt x \le 10000 \) 第三個數字 \( d，0 \lt d \lt 2^{64} \)

輸出格式

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

範例輸入

2 6 5

範例輸出

1