Коала Коа имеет бинарную строку \(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\)).
В первом примере Koa может получить следующие бинарные строки: \(0\), \(00\) и \(000\).
Во втором примере Коа может получить следующие бинарные строки: \(1\), \(01\), \(11\), \(011\), \(101\) и \(0101\). Например:
Круглые скобки обозначают две позиции, выбранные Коа в каждой операции.
000
3
0101
6
0001111
16
00101100011100
477
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач