Задана последовательность, состоящая из неотрицательных целых чисел. За один ход разрешается выбрать любые два соседних положительных числа и уменьшить их оба на 1. Последовательность называется хорошей, если нельзя совершить ни одного хода.

Вычислить количество хороших последовательностей, которое можно получить из заданной. Ответ может быть большим, поэтому его следует вывести по модулю 109 + 7.

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

Первая строка содержит длину последовательности n (1 ≤ n ≤ 105). Вторая строка содержит n неотрицательных целых чисел: начальную последовательность. Каждый элемент последовательности не превышает 300.

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

Вывести количество различных хороших последовательностей по модулю 109 + 7.