VSTEPS - Steps

no tags 

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 VB.NET
Resource:VNOI Marathon '08 - Round 1/DivB
Problem Setter: Ngô Minh Đức