H. Little t's Recurrence
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

Please note the special time limit and memory limit for this problem.

Little t has recently become very interested in fascinating number sequences and binary representations.

He defines a generalized recurrence sequence $$$f(i)$$$ with parameter $$$a$$$, formally given by: $$$$$$ f(i) = \begin{cases} 0 & \text{if } i = 0, \\ 1 & \text{if } i = 1, \\ a \cdot f(i-1) + f(i-2) & \text{if } i \ge 2. \end{cases} $$$$$$

At the same time, Little t defines the function $$$g(x)$$$ as the number of 1s in the binary representation of a positive integer $$$x$$$ (that is, the popcount). For example, $$$g(5) = g(101_{(2)}) = 2$$$.

Now, Little t has an extremely large positive integer $$$n$$$. Since it is too large, he can only write it as a binary string $$$s$$$ without leading zeros. He is also given the parameter $$$a$$$ of the recurrence sequence.

He really wants to know the value of the following summation: $$$$$$ \sum_{i=1}^{n} f(g(i)) \pmod{10^9+7} $$$$$$

However, since the number $$$n$$$ is far too large, Little t's computer was unable to compute the answer. Can you write a program to help him?

Input

The first line contains a string $$$s$$$ consisting only of 0 and 1 ($$$1 \le |s| \le 10^7$$$), representing the binary form of the number $$$n$$$. It is guaranteed that the first character is 1.

The second line contains a positive integer $$$a$$$ ($$$1 \le a \le 10^9$$$).

Output

Output one integer on a single line, representing the value of the summation required by Little t modulo $$$10^9+7$$$.

Example
Input
101
2
Output
7
Note

In the sample, the string 101 corresponds to the decimal number $$$n = 5$$$. The parameter is $$$a = 2$$$.

The first few terms of the sequence $$$f$$$ are computed as follows:

  • $$$f(0)=0$$$
  • $$$f(1)=1$$$
  • $$$f(2)=2 \times 1 + 0 = 2$$$

We need to compute the sum of $$$f(g(i))$$$ for $$$i$$$ from $$$1$$$ to $$$5$$$:

  • $$$i=1$$$ (1$$$_{(2)}$$$): $$$g(1)=1 \implies f(1)=1$$$
  • $$$i=2$$$ (10$$$_{(2)}$$$): $$$g(2)=1 \implies f(1)=1$$$
  • $$$i=3$$$ (11$$$_{(2)}$$$): $$$g(3)=2 \implies f(2)=2$$$
  • $$$i=4$$$ (100$$$_{(2)}$$$): $$$g(4)=1 \implies f(1)=1$$$
  • $$$i=5$$$ (101$$$_{(2)}$$$): $$$g(5)=2 \implies f(2)=2$$$

Therefore, the final answer is $$$1 + 1 + 2 + 1 + 2 = 7$$$.

The input and output size of this problem is large, so it is recommended to use fast I/O methods. For C++ contestants, it is recommended to use scanf/printf, or disable synchronization when using cin/cout:

std::ios::sync_with_stdio(false);

std::cin.tie(nullptr);