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

Dreamoon увидел большое целое число x, записанное на земле, теперь ему хочется вывести его в двоичной записи. Dreamoon успешно преобразовал x в двоичный формат. Теперь он собирается распечатать это число следующим образом.

У него есть целое число n = 0 и он может выполнять две следующие операции неограниченное количество раз в любом порядке:

  1. Распечатать двоичную запись n без ведущих нулей, результат печати добавляется справа к уже выведенной строке.
  2. Увеличить n на 1.

Определим идеальную последовательность как последовательность операций, которая может вывести двоичную запись x без ведущих нулей и заканчивается операцией 1. Dreamoon хочет знать, сколько существует различных идеальных последовательностей и какова длина (в операциях) наикратчайшей идеальной последовательности.

Ответы могут быть очень большими, поэтому выводите их по модулю 1 000 000 007 (109 + 7).

Определим строковое представление идеальной последовательности как строку из символов '1' и '2', где i-й символ в строке соответствует i-й выполненной операции. Две идеальные последовательности называются различными, если их строковые представления различны.

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

В единственной строке записано целое число в двоичной записи без ведущих нулей, обозначающее x (1 ≤ x < 25000).

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

В первой строке должно быть записано целое число — количество различных идеальных последовательностей по модулю 1 000 000 007 (109 + 7).

Во второй строке должно быть записано целое число — минимальная длина идеальной последовательности по модулю 1 000 000 007 (109 + 7).

Примеры
Входные данные
101
Выходные данные
1
6
Входные данные
11010
Выходные данные
3
5
Примечание

В первом примере наикратчайшая и единственная идеальная последовательность — «222221» длины 6.

Во втором примере существует три идеальных последовательности «21211», «212222222221», «222222222222222222222222221». Среди них кратчайшая имеет длину 5.