Зведення послідовності

Задано послідовність, що складається з невід'ємних цілих чисел. За один хід дозволяється вибрати будь-які два сусідніх додатних числа і зменшити їх обидва на 1. Послідовність називається хорошою, якщо жоден хід більше неможливий.

Потрібно обчислити кількість хороших послідовностей, які можна отримати з початкової. Оскільки відповідь може бути великою, виведіть її за модулем 10^9 + 7.

Вхідні дані

Перший рядок містить довжину послідовності n (1 ≤ n ≤ 10^5). Другий рядок містить n невід'ємних цілих чисел: початкову послідовність. Кожен елемент послідовності не перевищує 300.

Вихідні дані

Виведіть кількість різних хороших послідовностей за модулем 10^9 + 7.

Приклади