C. Fibonacci Sum
time limit per test
1 s
memory limit per test
512 megabytes
input
standard input
output
standard output

Let $$$f(i)$$$ denote the $$$i$$$-th number in the famous Fibonacci Sequence. Formally: $$$$$$f(i) = \begin{cases} 1 & \text{if } i \leq 2, \\ f(i-1) + f(i-2) & \text{if } i \gt 2. \end{cases} $$$$$$

Let $$$g(x)$$$ denote the count of $$$1$$$'s in the binary representation of number $$$x$$$. For example, $$$g(5)=g(101_{(2)})=2$$$, $$$g(15)=g(1111_{(2)})=4$$$.

Your task is to calculate the following value:

$$$$$$\sum_{i=1}^n f \left( g(i)\right) \bmod {10^9+7}$$$$$$

Input

The input contains a string $$$s$$$ ($$$1\le |s|\le 10^7$$$) consisting of only '0' or '1', denoting the number $$$n$$$ in binary form.

It's guaranteed that the input contains no leading $$$0$$$'s.

Output

The output contains a single integer, denoting the answer modulo $$$10^9+7$$$.

Examples
Input
1
Output
1
Input
10
Output
2
Input
11
Output
3
Note

It can be calculated that $$$f\left(g(1_{(2)})\right) = 1$$$, $$$f\left(g(10_{(2)})\right) = 1$$$, $$$f\left(g(11_{(2)})\right) = 1$$$.