У берега находится лягушка. Перед ней расположены камни с номерами от 1 до n, а берег считается позицией 0. За один прыжок лягушка может переместиться вперёд на 1 или на 2 позиции.

Часть камней раскрошилась, поэтому приземляться на них нельзя. Требуется определить, сколькими способами лягушка может добраться с берега до камня n.

Так как ответ может быть очень большим, выведите его по модулю 1000000007.

Входные данные

В первой строке задано целое число n — количество камней.

Во второй строке заданы n чисел b_i, где b_i равно 0, если камень i целый, и 1, если камень i сломан.

Выходные данные

Выведите одно число — количество различных маршрутов, по которым лягушка может попасть на камень n, по модулю 1000000007.

Если добраться до камня n невозможно, выведите 0.

Ограничения

• 1 <= n <= 2 * 10^5
• b_i принадлежит множеству {0, 1}

Примеры

Пример 1

Входные данные

5
0 0 1 0 0

Выходные данные

2

Пояснение

Камень 3 сломан; до камня 5 ведут 2 маршрута.

Пример 2

Входные данные

1
0

Выходные данные

1

Пример 3

Входные данные

2
1 1

Выходные данные

0