D. Meaningless Sequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 \lt 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.

Input

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

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

Output

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

Example
Input
1000 3
Output
67