Submit | All submissions | Best solutions | Back to list |
VSTEPS - Steps |
English | Vietnamese |
While playing the computer game "Lucky Luke", Bom arrived at a scenario in which Lucky has to climb a staircase consisting of n steps.
The steps are numbered as 1 to n from bottom to top. Lucky may go up one step, or may jump two steps at once. However, some steps are broken and Lucky cannot stand on them. In the beginning, Lucky stands on the first step (the first step is never broken).
Suddenly, Bom arrived at a question: how many ways for Lucky to climb the staircase? (i.e. to stand on the nth step). Bom needs your help to answer this question.
Input
- The first line consisting of two integers n and k; n is the number of steps in the staircase and k is the number of broken steps (0 ≤ k < n ≤ 100000).
- The second line consisting of k integers which are the indexes of the broken steps in ascending order.
Output
Print out the remainder of the number of ways for Lucky to climb the staircase when divided to 14062008.
Examples
Input 4 2 2 3 Output 0 Input 90000 1 49000 Output 4108266
Added by: | VOJ Team |
Date: | 2008-06-13 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 SCM qobi VB.NET |
Resource: | VNOI Marathon '08 - Round 1/DivB Problem Setter: Ngô Minh Đức |