\(N\) (\(1 \leq N \leq 100\)) корів Фермера Джона вишикувані в ряд так, що \(i\)-а корова має рівень голоду \(h_i\) (ціле невід'ємне число). Корови хочуть їсти разом, і єдиний спосіб зменшити рівень голоду його корів – вибрати сусідню пару корів \(i\) і \(i+1\) і дати кожній з них мішок кукурудзи, тим самим зменшити на 1 рівень голоду кожної з них.

ФД хоче годувати своїх корів доки у всіх них не стане один і той самий рівень голоду

• цілий, невід'ємний. Хоча він не знає точно рівень голоду кожної зі своїх корів, він знає верхню межу рівня голоду кожної корови, тобто рівень голоду \(i\)-ой cow \(h_i\) не більше \(H_i\) (\(0\le H_i\le 1000\)).

Ваше завдання - порахувати за модулем \(10^9+7\) кількість комбінацій з \(N\) рівнів голоду \([h_1,h_2,\ldots,h_N]\) таких, що ФД зможе досягти своєї мети.

Формат вхідних даних

Перший рядок містить число \(N\).

Другий рядок містить \(H_1,H_2,\ldots,H_N\).

Формат вихідних даних

Кількість комбінацій із \(N\) чисел рівнів голоду за модулем \(10^9+7\).

Приклад вхідних даних

3
9 11 7

Приклад вихідних даних

241

Всього є \((9+1)\cdot (11+1)\cdot (7+1)\) комбінацій з \(3\) чисел \(h\) які задовольняють \(H\).

Одна з таких трійок \(h=[8,10,5]\). У цьому випадку можна зробити всім коровам той самий рівень голоду: даємо по 2 мішки кукурудзи коровам \(2\) і \(3\), потім даємо по 5 мішків кукурудзи коровам \(1\) і \(2\), в результаті отримаємо рівень голоду \(3\) у всіх корів.

Для трійки \(h=[0,1,0]\) неможливо зробити рівні голоду однаковими.

Приклад вхідних даних

4
6 8 5 9

Приклад вихідних даних

137

ОЦІНЮВАННЯ:

\(N\) парне у тестах з парними номерами та непарне у тестах з непарними номерами.

• У тестах 3 і 4 \(N\le 6\) і \(H_i \le 10\).

• У тестах 5 - 10 \(N\le 50\) і \(H_i \le 100\).

• У тестах 11 – 20 немає додаткових обмежень.