令 $f(i)$ 表示著名的斐波那契数列中的第 $i$ 项。形式化定义如下：

$$f(i) = \begin{cases} 1 & \text{if } i \le 2, \\ f(i - 1) + f(i - 2) & \text{if } i > 2. \end{cases}$$

令 $g(x)$ 表示数字 $x$ 的二进制表示中 $1$ 的个数。例如，$g(5) = g(101_{(2)}) = 2$，$g(15) = g(1111_{(2)}) = 4$。

你的任务是计算以下值：

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

输入格式

输入包含一个字符串 $s$ ($1 \le |s| \le 10^7$)，仅由 '0' 或 '1' 组成，表示二进制形式的数字 $n$。

保证输入不包含前导零。

输出格式

输出一个整数，表示答案对 $10^9 + 7$ 取模的结果。

样例

输入格式 1

1

输出格式 1

1

输入格式 2

10

输出格式 2

2

输入格式 3

11

输出格式 3

3

说明

可以计算得出 $f(g(1_{(2)})) = 1$，$f(g(10_{(2)})) = 1$，$f(g(11_{(2)})) = 1$。