Dreamoon and Binary

题意翻译

有一台特殊的打印机，这台打印机内置一个初始为 0 可以任意大的整数 ? 和一个 初始为空的串，该打印机除了初始化之外，还可以进行下述两种操作： 1、 在当前串末尾打印 ? 的不带前导 0 的二进制表示串（即末尾添加串） 2、 令 ? = ? + 1 现在要求打印机恰好打印出这个串。在此基础上，最少需要进行几次操作才可以将这个 01 串打印出来，以及有多少种方案能够打印出这个串，由于这两个数可能过大，因 此你只需要输出其模1e9 + 7的结果。

题目描述

Dreamoon saw a large integer $ x $ written on the ground and wants to print its binary form out. Dreamoon has accomplished the part of turning $ x $ into its binary format. Now he is going to print it in the following manner. He has an integer $ n=0 $ and can only perform the following two operations in any order for unlimited times each: 1. Print n in binary form without leading zeros, each print will append to the right of previous prints. 2. Increase n by 1. Let's define an ideal sequence as a sequence of operations that can successfully print binary representation of $ x $ without leading zeros and ends with a print operation (i.e. operation 1). Dreamoon wants to know how many different ideal sequences are there and the length (in operations) of the shortest ideal sequence. The answers might be large so please print them modulo 1000000007 ( $ 10^{9}+7 $ ). Let's define the string representation of an ideal sequence as a string of '1' and '2' where the $ i $ -th character in the string matches the $ i $ -th operation performed. Two ideal sequences are called different if their string representations are different.

输入输出格式

输入格式

The single line of the input contains a binary integer representing $ x $ ( $ 1<=x<2^{5000} $ ) without leading zeros.

输出格式

The first line of the output should contain an integer representing the number of different ideal sequences modulo 1000000007 ( $ 10^{9}+7 $ ). The second line of the output contains an integer representing the minimal length of an ideal sequence modulo 1000000007 ( $ 10^{9}+7 $ ).

输入输出样例

输入样例 #1

101

输出样例 #1

1
6

输入样例 #2

11010

输出样例 #2

3
5

说明

For the first sample, the shortest and the only ideal sequence is «222221» of length $ 6 $ . For the second sample, there are three ideal sequences «21211», «212222222221», «222222222222222222222222221». Among them the shortest one has length $ 5 $ .