Description

Time flies, the sun and the moon are like a shuttle. Mosu has been through the years of study, got the offers of the major first-line companies, is considering how to choose a suitable company. So she decided to relax with a simple little game. This is a game that is generated into a binary string. It is not as simple as it is to play with it. So I would like to ask you to help her to think about this issue. The problem is this: for a number n, each step can select one of the two operations as below:

a. Append a binary string of the number n to the binary string that has been generated

b. Add one to n

Now the n is initial 0, please answer the number of methods to construct the target string $s$ and the minimum number of steps to construct the target string.

Format

Input

The input contains a target string $s$ which need be generated in one line, the case ensures that the string without leading zero. ($|s| \leq 5000$)

Output

In the first line, print the number of methods she can generate n to $s$.

In the second line, print the minimum number of steps.

Due to the two numbers maybe enormous, so print the value of module of $10^9 + 7$.

Samples

11010

3
5

Hint

The three mothods are 'babaa', 'babbbbbbbbba',and 'bbbbbbbbbbbbbbbbbbbbbbbbbba'.And the minimum steps is 5.