1423 . 反費波那契數列
TopCoder
Tags
Description
小卷是自然番茄大學（Natural Tomato University, NTU）的交換生，正如他的名字一樣，從小就在卷。
小卷在三個月大時從書上看到了一個序列：費波那契數列（Fibonacci sequence），內卷的他立刻就不高興了。Fibonacci 的開頭字母是 F，F is for FAILURE!!!，怎麼會有這麼爛的序列呢？
因此，他決定要創造一個序列：反費波那契數列（Anti-Fibonacci sequence）。這個新數列的開頭字母現在是 A，跟他的成績一樣，他高興了。
他決定順水推舟下去定義，反費波那契數列的核心定義應該要把費波那契數列的定義反過來，也就是說，對於所有的 $i$，都應該要滿足 $A_i + A_{i+1} \neq A_{i+2}$。除此之外的部分都保持原狀，也就是說反費波那契數列仍然是一個正整數數列。另外，由於他喜歡數數，因此反費波那契數列要跟費波那契數列一樣是非嚴格遞增的。
現在，他很好奇，有多少個 $N$ 項，最大值不超過 $M$ 的反費波那契數列，為了方便起見，他選擇了一個模數 $P$，請你將答案模 $P$ 後輸出。
Input Format
輸入只有一行，為三個整數 $N$, $M$, $P$。
- $1 \leq N \leq 2000$
- $1 \leq M \leq 5000$
- $10^ 8 \leq P \leq 10^ 9$
Output Format
輸出一個整數，代表反費波那契數列的數量模 $P$ 的結果。
Sample Input 1
3 3 535635271
Sample Output 1
8
Sample Input 2
5 6 980575740
Sample Output 2
170
Sample Input 3
2000 5000 194410966
Sample Output 3
130665979
Hints
在第一筆範例測試中，所有的反費波那契數列如下：
- $[1, 1, 1]$
- $[1, 1, 3]$
- $[1, 2, 2]$
- $[1, 3, 3]$
- $[2, 2, 2]$
- $[2, 2, 3]$
- $[2, 3, 3]$
- $[3, 3, 3]$
這首歌可能不會有用，畢竟他是反費波那契數列嘛。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資。 | 0 |
| 2 | 3~12 | $N \leq 80, M \leq 80$ | 10 |
| 3 | 3~22 | $N \leq 500, M \leq 500$ | 20 |
| 4 | 0~32 | 無特別限制。 | 70 |