Giải bài trực tuyến

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 n^th 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