Трава висохла на пасовищі фермера Джона через посуху. Після годин відчаю та роздумів ФД придумав прекрасну ідею купити кукурудзу, щоб годувати своїх дорогоцінних корів.

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

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

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

Input

Перший рядок містить ~N~.

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

Output

Кількість ~N~-масивів рівнів голоду за модулем ~10^9+7~.

Оцінювання

~N~ парне у випадках з парним номером тестів і непарне в випадках з непарним номером тестів.

• Для ~20~ балів ~N\le 6~ та ~H_i \le 10~.

• Для ~50~ балів ~N\le 50~ та ~H_i \le 100~.

Notes

Перший приклад:

Є ~(9+1)\cdot(11+1)\cdot(7+1)~ ~3~-масиви ~h~, які узгоджуються з ~H~.

Один з цих масивів - ~h=[8,10,5]~. В цьому випадку можна зробити всі корови з однаковими рівнями голоду: дайте по два мішки кукурудзи обом коровам ~2~ та ~3~, тоді дайте по п'ять мішків кукурудзи обом коровам ~1~ та ~2~, що призведе до того, що кожна корова матиме рівень голоду ~3~.

Інший з цих масивів - ~h=[0,1,0]~. В цьому випадку не можна зробити рівні однаковими.