Будем говорить, что бесконечная последовательность \(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\).
Примечание
Рассмотрим первый пример. На данном поле клетки \((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\) операций.