#include #include using namespace std; using namespace atcoder; typedef long long int ll; typedef long double ld; typedef vector vi; typedef vector vl; typedef vector vvl; typedef vector vvvl; typedef vector vvvvl; typedef vector vb; typedef vector vvb; typedef vector vvvb; typedef vector vvvvb; typedef pair pl; typedef pair ppl; typedef pair pppl; typedef pair pppppl; #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--) #define all(a) begin(a),end(a) #define sz(a) (int)(a).size() #define F first #define S second #define bs(A,x) binary_search(all(A),x) #define lb(A,x) (ll)(lower_bound(all(A),x)-A.begin()) #define ub(A,x) (ll)(upper_bound(all(A),x)-A.begin()) #define cou(A,x) (ll)(upper_bound(all(A),x)-lower_bound(all(A),x)) templateusing min_priority_queue=priority_queue,greater>; templatebool chmax(T&a,T b){if(abool chmin(T&a,T b){if(b vm; typedef vector vvm; typedef vector vvvm; typedef vector vvvvm; ostream&operator<<(ostream&os,mint a){os<>(istream&is,mint&a){int x;is>>x;a=mint(x);return is;} //*/ templateostream&operator<<(ostream&os,pairp){os<istream&operator>>(istream&is,pair&p){is>>p.F>>p.S;return is;} templateostream&operator<<(ostream&os,vectorv){rep(i,0,sz(v))os<istream&operator>>(istream&is,vector&v){for(T&in:v)is>>in;return is;} int main(){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); string S;ll K;cin>>S>>K; ll N=sz(S); vvm X(3,vm(3)),Y(3,vm(3)),Z(3,vm(3)); X[0][0]=X[1][1]=1; rep(i,0,N){ vvm _X=X,_Y=Y,_Z=Z; if(S[i]=='0'){ _X[0][0]+=X[0][1];_X[1][0]+=X[1][1]; _Y[0][0]+=Y[0][1]+X[0][1];_Y[1][0]+=Y[1][1]+X[1][1]; _Z[0][0]+=Z[0][1]+2*Y[0][1]+X[0][1];_Z[1][0]+=Z[1][1]+2*Y[1][1]+X[1][1]; } else{ _X[0][1]+=X[0][0];_X[1][1]+=X[1][0]; _Y[0][1]+=Y[0][0]+X[0][0];_Y[1][1]+=Y[1][0]+X[1][0]; _Z[0][1]+=Z[0][0]+2*Y[0][0]+X[0][0];_Z[1][1]+=Z[1][0]+2*Y[1][0]+X[1][0]; } X=_X;Y=_Y;Z=_Z; } X[2][0]=X[0][0]+X[1][0]-1; X[2][1]=X[0][1]+X[1][1]-1; X[2][2]=1; Y[2][0]=Y[0][0]+Y[1][0]; Y[2][1]=Y[0][1]+Y[1][1]; Z[2][0]=Z[0][0]+Z[1][0]; Z[2][1]=Z[0][1]+Z[1][1]; vvvvm dou(3,vvvm(60,vvm(3,vm(3)))); dou[0][0]=X;dou[1][0]=Y;dou[2][0]=Z; rep(j,1,60){ rep(x,0,3)rep(y,0,3)rep(z,0,3){ dou[0][j][x][z]+=dou[0][j-1][x][y]*dou[0][j-1][y][z]; dou[1][j][x][z]+=dou[1][j-1][x][y]*dou[0][j-1][y][z]+dou[0][j-1][x][y]*dou[1][j-1][y][z]; dou[2][j][x][z]+=dou[2][j-1][x][y]*dou[0][j-1][y][z]+2*dou[1][j-1][x][y]*dou[1][j-1][y][z]+dou[0][j-1][x][y]*dou[2][j-1][y][z]; } } vvm DP(3,vm(3)); DP[0][2]=1; rep(i,0,60)if((K>>i)%2){ vvm EP(3,vm(3)); rep(x,0,3)rep(y,0,3){ EP[0][y]+=DP[0][x]*dou[0][i][x][y]; EP[1][y]+=DP[0][x]*dou[1][i][x][y]+DP[1][x]*dou[0][i][x][y]; EP[2][y]+=DP[0][x]*dou[2][i][x][y]+2*DP[1][x]*dou[1][i][x][y]+DP[2][x]*dou[0][i][x][y]; } DP=EP; } cout<<(DP[2][0]+DP[2][1]).val()<