t = input()
k = int(input())
mod = 10 ** 9 + 7

dp = [[0, 0, 0], [0, 0, 1], [0, 0, 1], [0, 0, 0]] 
from copy import deepcopy as cp
for i in range(len(t)):
    ndp = cp(dp)
    a = int(t[i])
    for j in range(4):
        if j & 1 != a:
            ndp[j^1][0] += dp[j][0] + 2 * dp[j][1] + dp[j][2]; ndp[j^1][0] %= mod
            ndp[j^1][1] += dp[j][1] + dp[j][2]; ndp[j^1][1] %= mod
            ndp[j^1][2] += dp[j][2]; ndp[j^1][2] %= mod
    dp = ndp

B = dp
ans = [[0, 0, 0], [0, 0, 1], [0, 0, 1], [0, 0, 0]] 
while k:
    if k & 1:
        ndp = [[0, 0, 0] for _ in range(4)]
        for i in range(4):
            for j in range(4):
                if i & 1 != (j >> 1) & 1:
                    nxt = (i & 2) | (j & 1)
                    ndp[nxt][0] += ans[i][0] * B[j][2] + ans[i][2] * B[j][0] + 2 * ans[i][1] * B[j][1]; ndp[nxt][0] %= mod
                    ndp[nxt][1] += ans[i][1] * B[j][2] + ans[i][2] * B[j][1]; ans[nxt][1] %= mod
                    ndp[nxt][2] += ans[i][2] * B[j][2]; ndp[nxt][2] %= mod
        ans = ndp
    ndp = [[0, 0, 0] for _ in range(4)]
    for i in range(4):
        for j in range(4):
            if i & 1 != (j >> 1) & 1:
                nxt = (i & 2) | (j & 1)
                ndp[nxt][0] += B[i][0] * B[j][2] + B[i][2] * B[j][0] + 2 * B[i][1] * B[j][1]; ndp[nxt][0] %= mod
                ndp[nxt][1] += B[i][1] * B[j][2] + B[i][2] * B[j][1]; ndp[nxt][1] %= mod
                ndp[nxt][2] += B[i][2] * B[j][2]; ndp[nxt][2] %= mod
    B = ndp
    k >>= 1

Ans = 0
for i in range(4):
    Ans += ans[i][0]; Ans %= mod
print(Ans)