#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#include <atcoder/modint>
using mint=atcoder::modint1000000007;
int main(){
	string s;
	cin>>s;
	ll k;
	cin>>k;
	vector<vector<vector<mint>>> mat(2,vector<vector<mint>>(6,vector<mint>(6)));
	for(int i=0;i<6;i++){
		mat[0][i][i]=1;
		mat[1][i][i]=1;
	}
	mat[0][0][3]=1;mat[0][1][3]=1;mat[0][1][4]=1;mat[0][2][3]=1;mat[0][2][4]=2;mat[0][2][5]=1;
	mat[1][3][0]=1;mat[1][4][0]=1;mat[1][4][1]=1;mat[1][5][0]=1;mat[1][5][1]=2;mat[1][5][2]=1;
	vector<vector<mint>> t(6,vector<mint>(6));
	for(int i=0;i<6;i++)t[i][i]=1;
	auto prod=[](vector<vector<mint>> x,vector<vector<mint>> y)->vector<vector<mint>>{
		vector<vector<mint>> res(6,vector<mint>(6));
		for(int i=0;i<6;i++)for(int j=0;j<6;j++)for(int k=0;k<6;k++){
			res[i][j]+=x[i][k]*y[k][j];
		}
		return res;
	
	};
	int n=s.size();
	for(int i=0;i<n;i++)t=prod(mat[s[i]-'0'],t);
	vector<vector<mint>> res(6,vector<mint>(6));
	for(int i=0;i<6;i++)res[i][i]=1;
	while(k>0){
		if(k&1){
			res=prod(t,res);
		}
		t=prod(t,t);
		k>>=1;
	}
	vector<mint> v(6);
	for(int i=0;i<6;i++)for(int j=0;j<6;j++)v[i]+=res[i][j];
	cout<<(v[2]-2*v[1]+v[0]+v[5]-2*v[4]+v[3]).val()<<endl;
}