Коала Коа имеет бинарную строку \(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\))?
Выходные данные
В единственной строке выведите ответ на задачу по модулю \(10^9+7\) (\(1000000007\)).
Примечание
В первом примере 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\).
Круглые скобки обозначают две позиции, выбранные Коа в каждой операции.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
000
|
3
|
|
2
|
0101
|
6
|
|
3
|
0001111
|
16
|
|
4
|
00101100011100
|
477
|