Question
The Staircase of Destiny
You are standing at the bottom (stair 0) of a magical staircase that has n steps. Some of these steps are cursed (broken) and cannot be stepped on.
You can move up the staircase by taking either 1 step or 2 steps at a time. However, you must avoid all cursed steps, otherwise you will fall and fail the journey.
Your task is to determine how many distinct ways there are to reach the top step (n) safely. If it’s impossible to reach the top because of the cursed steps, return 0.
Note: You always start at the 0-th step
Input
The first line contains two integers n and m — the total number of steps, and the number of cursed (broken) steps.
The second line contains m space-separated integers — the indices of the cursed steps.
The second line contains m space-separated integers — the indices of the cursed steps.
Output
Print the total number of distinct ways to reach step n without stepping on cursed steps.
Example
Sample Input
3 1
2
Sample Output
1
Explanation
There are 1 ways to climb to the nth stair.
0 -> 1 -> 3
Sample Input
5 2
1 3
Sample Output
1
Explanation
There are 1 ways to climb to the 5th stair:
0 → 2 → 4 → 5
Sample Input
5 1
1
Sample Output
3
There are 3 ways to climb to the 5th stair:
0 → 2 → 3 → 4 → 5
0 → 2 → 4 → 5
0 → 2 → 3 → 5
3 1
2
Sample Output
1
Explanation
There are 1 ways to climb to the nth stair.
0 -> 1 -> 3
Sample Input
5 2
1 3
Sample Output
1
Explanation
There are 1 ways to climb to the 5th stair:
0 → 2 → 4 → 5
Sample Input
5 1
1
Sample Output
3
There are 3 ways to climb to the 5th stair:
0 → 2 → 3 → 4 → 5
0 → 2 → 4 → 5
0 → 2 → 3 → 5