E. Размещение кукол
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Будем говорить, что бесконечная последовательность $$$a_{0}, a_{1}, a_2, \ldots$$$ является невозрастающей, если и только если $$$a_i \ge a_{i+1}$$$ для всех $$$i\ge 0$$$.

Дано бесконечное вправо и вниз клетчатое поле. Верхняя левая клетка имеет координаты $$$(0,0)$$$. Строки пронумерованы от $$$0$$$ до бесконечности сверху вниз, столбцы пронумерованы от $$$0$$$ до бесконечности слева направо.

Также дана невозрастающая бесконечная последовательность $$$a_{0}, a_{1}, a_2, \ldots$$$. Вам заданы $$$a_0$$$, $$$a_1$$$, $$$\ldots$$$, $$$a_n$$$. Также известно, что $$$a_i=0$$$ для всех $$$i>n$$$. Для любой пары $$$x$$$, $$$y$$$ клетка с координатами $$$(x,y)$$$ (расположенная на пересечении $$$x$$$-й строки и $$$y$$$-го столбца) покрашена в белый цвет, если $$$y<a_x$$$, а иначе покрашена в чёрный.

Изначально на всём поле есть лишь одна кукла, расположенная в клетке $$$(0,0)$$$. Вы можете выполнять следующую операцию.

  • Выбрать одну куклу в клетке $$$(x,y)$$$. Затем удалить её и добавить по кукле в клетки $$$(x,y+1)$$$ и $$$(x+1,y)$$$.

Обратите внимание, что в одной клетке одновременно может находиться несколько кукол; за одну операцию вы удаляете только одну куклу. Ваша цель — сделать так, чтобы во всех белых клетках было ровно $$$0$$$ кукол.

Чему равно минимальное число операций, за которое можно достичь этой цели? Выведите ответ по модулю $$$10^9+7$$$.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$).

Вторая строка содержит $$$n+1$$$ целых чисел: $$$a_0,a_1,\ldots,a_n$$$ ($$$0\le a_i\le 2\cdot 10^5$$$).

Гарантируется, что последовательность $$$a$$$ является невозрастающей.

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

Выведите одно число — ответ на задачу по модулю $$$10^9+7$$$.

Примеры
Входные данные
2
2 2 0
Выходные данные
5
Входные данные
10
12 11 8 8 6 6 6 5 3 2 1
Выходные данные
2596
Примечание

Рассмотрим первый пример. На данном поле клетки $$$(0,0),(0,1),(1,0),(1,1)$$$ являются белыми, а все остальные — чёрными. Для описания поля будем использовать тройки: тройка $$$(x,y,z)$$$ означает, что в клетке $$$(x,y)$$$ расположено $$$z$$$ кукол. Изначальное состояние поля: $$$(0,0,1)$$$.

Одной из оптимальных последовательностей операций является следующая:

  • Выполнить операцию для $$$(0,0)$$$. Состояние поля станет таким: $$$(1,0,1),(0,1,1)$$$.
  • Выполнить операцию для $$$(0,1)$$$. Состояние поля станет таким: $$$(1,0,1),(1,1,1),(0,2,1)$$$.
  • Выполнить операцию для $$$(1,0)$$$. Состояние поля станет таким: $$$(1,1,2),(0,2,1),(2,0,1)$$$.
  • Выполнить операцию для $$$(1,1)$$$. Состояние поля станет таким: $$$(1,1,1),(0,2,1),(2,0,1),(1,2,1),(2,1,1)$$$.
  • Выполнить операцию для $$$(1,1)$$$. Состояние поля станет таким: $$$(0,2,1),(2,0,1),(1,2,2),(2,1,2)$$$.

После этого все белые клетки содержат по $$$0$$$ кукол, так что цель достигнута за $$$5$$$ операций.