4489. 魔力数字

【题目背景】

一天数学课上，豆包有了神奇的发现。

【题目描述】

豆包在研究一种神奇的数字能量。对于任意正整数 $x$，定义它的闪耀度 $g(x)$ 为 $x$ 在二进制表示下数码 $1$ 的个数。例如 $g(5)=g(101_{(2)})=2$。

此外，豆包定义了一个闪耀能量数列 $f$，该数列依赖于一个正整数参数 $a$，并满足如下递推关系：

$f_0=0,f_1=1,f_i=a \cdot f_{i-1}+f_{i-2} (if  i \ge 2)$

现在豆包得到了一个巨大的数字 $n$，以二进制形式给出（保证没有前导零）。他想知道，从 $1$ 到 $n$ 的所有整数中，每个数的闪耀度对应的闪耀能量之和是多少。即求

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

请你帮豆包计算这个值。

大样例

【输入格式】

第一行一个仅由 0 和 1 组成的字符串 $s$，表示数字 $n$ 的二进制形式，保证首位为 1。

第二行一个正整数 $a$，即闪耀能量数列的参数。

【输出格式】

输出一行一个整数，表示求和结果对 $10^9+7$ 取模后的值。

【样例输入】

101
2

【样例输出】

7

【样例说明】

$s=101$ 对应 $n=5$，参数 $a=2$。

闪耀能量数列的前几项：

$f(0)=0,f(1)=1,f(2)=2\times1+0=2$

计算 $i$ 从 $1$ 到 $5$ 的 $f(g(i))$：

$i=1 (1_{2}) : g(1)=1，f(1)=1$ 

$i=2 (10_{2}) : g(2)=1，f(1)=1$

$i=3 (11_{2}) : g(3)=2，f(2)=2$

$i=4 (100_{2}) : g(4)=1，f(1)=1$ 

$i=5 (101_{2}) : g(5)=2，f(2)=2$

$总和为 1+1+2+1+2=7。$

【数据规模与约定】

对于所有数据点:

$1: | s | \le 20 $

$2: n$ 的数位全为 $1$

$3: |s| \le 1000,a=1$   

$4: |s| \le 1000$

$5: |s| \le 10^6,a=1$

$6: |s| \le 10^6$

$7: a=1$

$8,9.10:$ 无任何限制

对于 $100%$ 的数据，$1 \le |s| \le 10^7$，$1 \le a \le 10^9。$

【来源】

好题