E. Странная операция
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Коала Коа имеет бинарную строку $$$s$$$ длины $$$n$$$. Коа может выполнить не более $$$n-1$$$ (возможно, ноль) операций следующего вида:

За одну операцию Коа выбирает позиции $$$i$$$ и $$$i+1$$$ для некоторого $$$i$$$ с $$$1 \le i < |s|$$$ и делает $$$s_i$$$ равным $$$max(s_i, s_{i+1})$$$. Затем Коа удаляет позицию $$$i+1$$$ из $$$s$$$ (после удаления оставшиеся части склеиваются).

Обратите внимание, что после каждой операции длина $$$s$$$ уменьшается на $$$1$$$.

Сколько разных бинарных строк может получить Коа, выполнив не более $$$n-1$$$ (возможно, ноль) операций по модулю $$$10^9+7$$$ ($$$1000000007$$$)?

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

Единственная строка ввода содержит бинарную строку $$$s$$$ ($$$1 \le |s| \le 10^6$$$). Для всех $$$i$$$ ($$$1 \le i \le |s|$$$) $$$s_i = 0$$$ или $$$s_i = 1$$$.

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

В единственной строке выведите ответ на задачу по модулю $$$10^9+7$$$ ($$$1000000007$$$).

Примеры
Входные данные
000
Выходные данные
3
Входные данные
0101
Выходные данные
6
Входные данные
0001111
Выходные данные
16
Входные данные
00101100011100
Выходные данные
477
Примечание

В первом примере Koa может получить следующие бинарные строки: $$$0$$$, $$$00$$$ и $$$000$$$.

Во втором примере Коа может получить следующие бинарные строки: $$$1$$$, $$$01$$$, $$$11$$$, $$$011$$$, $$$101$$$ и $$$0101$$$. Например:

  • для получения $$$01$$$ из $$$0101$$$ Коа может действовать следующим образом: $$$0101 \rightarrow 0(10)1 \rightarrow 011 \rightarrow 0(11) \rightarrow 01$$$.
  • для получения $$$11$$$ от $$$0101$$$ Коа может действовать следующим образом: $$$0101 \rightarrow (01)01 \rightarrow 101 \rightarrow 1(01) \rightarrow 11$$$.

Круглые скобки обозначают две позиции, выбранные Коа в каждой операции.