Задача
Любимая шахматная фигура Громозеки - это ладья. Но он любит ходить ей только по вертикали, причем либо на одну клетку, либо на две. Громозека заканчивает игру, когда ладья доходит до конца вертикали. Подумав над очередной позицией, он заметил, что некоторые клетки на пути ладьи находятся под ударом фигур соперника и ходить на эти клетки нельзя.
Помогите Громозеке посчитать сколькими способами он может перевести ладью c 1 горизонтали на другой конец шахматного поля, не попадая на клетки под ударом.
Входные данные
В первой строке вводится одно натуральное число
N (N <= 40): размер шахматного поля. Во второй строке вводится одно натуральное число
K (K <= N): количество клеток, находящихся под ударом. В третьей строке вводятся
K различных натуральных чисел в диапазоне от
1 до
N: номера клеток, находящихся под ударом фигур соперника.
Выходные данные
Выведите одно число - количество способов попасть на конец вертикали (на
N-ю клетку).
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
7
2
3 5 |
1 |
| 2 |
10
3
5 1 2 |
0 |
| 3 |
3
1
2 |
1 |