大獅子想要走上一個有 $n$ 階的樓梯
因為他是一隻大獅子,所以他一步可以走 $1$ 到 $n$ 階樓梯
也因為他是一隻大獅子,所以他決定不能一步走 $a_1, a_2, ... , a_m$ 階樓梯,保證所有 $a_i$ 都不重複
大獅子威脅你幫他算有幾種方法可以走到第 $n$ 階樓梯
你感覺性命受到威脅,所以你要回答大獅子的問題
答案可能很大,大獅子無法理解很長的數字,所以請輸出答案除以 $10^9+7$ 的餘數
$1 \leq n \leq 10^5$
$0 \leq m \leq 100$
$1 \leq a_i \leq n$
第一行包括兩個正整數$n, m$分別代表階梯數和不能一步走的階數數量
第二行有m個正整數$a_1, a_2, ... , a_m$,代表大獅子不能一步走的階數
輸出一個數字:大獅子走到第$n$階的方法數除以$10^9+7$的餘數
5 2 3 2
4
41538 8 22527 13027 32757 15384 18096 32050 13396 39172
203863375
範測 1 中大獅子能:
1 1 1 1 1
1 4
4 1
5
共四種走法
而 1 2 2 這種不行,因為他不能一步走 2 或 3 階樓梯
ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |