407576: GYM102832 D Meaningless Sequence

Once there was a mathematician, who was obsessed with meaningless number sequences. Here is one of them.

$$$$$$a_n = \begin{cases} 1, & n = 0 \\ c \cdot \max\limits_{0 \leq i < n} a_{n \operatorname{\&} i}, & \text{otherwise} \end{cases},$$$$$$ where $$$\operatorname{\&}$$$ denotes the bitwise AND operation.

As a mathematician, he could easily tell what $$$a_n$$$ was for any $$$n$$$, but he wanted to test you. You are required to tell him

$$$$$$\left( \sum\limits_{i=0}^n a_i \right) \bmod (10^9+7)$$$$$$

to convince him that you have a deep understanding of this (although meaningless) sequence.

The only line contains two integers $$$n$$$ and $$$c$$$ ($$$0 \leq n < 2^{3000}, 0 \leq c \leq 10^9)$$$.

Specially, $$$n$$$ is given in binary presentation. $$$c$$$ is given in decimal presentation normally.

Print what you are expected to tell the mathematician normally in decimal presentation.

1000 3

67