c560. SF 愛運動
Tags :
Accepted rate : 211人/234人 ( 90% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-10-23 16:53

Content

一年一度的 101 大樓爬樓梯競賽始報名囉,喜歡運動的 StillFantasy (以下簡稱 SF ) 毫不猶豫的馬上報名參加。

現在 101 大樓共有 N 階樓梯,每個參賽者都必須從第 0 階走到最後一階(也就是第 N 階),且主辦單位在某些階樓梯設有休息站(一定要剛好走到那階樓梯),提供礦泉水及 Kinder 巧克力 等零食給選手補充體力。

 

聰明的 SF 想了一個絕對能贏的方法 :

1. 每步可以選擇走三階(EX 0 -> 3)或走一階(EX 0 -> 1 )

2. 必須到每個休息站休息及吃一個 Kinder 以維持體力。

 

現在無聊的 CTF 想知道 SF 完成比賽的方法數,請你寫個程式幫助 CTF 算出答案。

Input

第一行共兩個數字 n 跟 m ,分別代表 101 大樓的階梯總數及休息站的數量。

(1 <= n <= 100000 , 0 <= m < n)

接下來一行共 m 個數字 a [ i ] ( 1 <= a [ i ] < n ) ,代表每個休息站所在的階梯,且 a [ i ] < a [ i + 1]。

Output

輸出一個數,代表 SF 完成比賽的方法數。

答案可能很大,請 mod 1000000007 。

Sample Input #1
5 1
3
Sample Output #1
2
測資資訊:
記憶體限制: 128 MB
不公開 測資點#0 (5%): 1.0s , <1K
不公開 測資點#1 (5%): 1.0s , <1K
不公開 測資點#2 (15%): 1.0s , <1K
不公開 測資點#3 (15%): 1.0s , <1M
不公開 測資點#4 (15%): 1.0s , <1M
不公開 測資點#5 (15%): 1.0s , <1M
不公開 測資點#6 (15%): 1.0s , <1M
不公開 測資點#7 (15%): 1.0s , <1M
Hint :

範例輸入 :

0 -> 1 -> 2 -> 3 (休息站) -> 4 -> 5

0 -> 3 (休息站) -> 4 -> 5

 

1. 10 % 的測資 n <= 10, m <=  1

2. 15 % 的測資 n <= 50, m <= 10

3. 75 % 的測資,無其他限制

Tags:
出處:
[管理者: andy89923 (CTFang) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
44168 s10900156@nh ... (ShanC) c560
42 2024-11-08 23:20
41151 xsw20080329@ ... (敢不敢讓我過) c560
95 2024-07-08 11:01