#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll __uint128_t
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 300005
#define inf 0x3f3f3f3f

bool add(ll&x,ll y){
	if(x<=(~y))return x+=y,0;
	return x=0,x--,1;
}

int n,k;
ll f[maxn];

bool chk(){
	if(n<=200)return 0;
	ll res=0;
	if(add(res,f[n]))return 1;
	For(i,1,k*2)
		if(i%(k*2+1)!=0 && add(res,f[n-i]))return 1;
	return 0;
}

void init_dp(int K){
	k=K;
	f[0]=1,f[1]=1,n=1;
	while(!chk()){
		++n;
		f[n]=f[n-1];
		if(n>=2*k+1)add(f[n],f[n-(2*k+1)]);
	}
}

int pigeon_num(int Taskid,int K){
	init_dp(K);
	return n;
}

string s;
void dfs(int n,ll x){
	if(!n)return;
	if(x<f[n-1]){
		s+='0';
		dfs(n-1,x);
	}else{
		For(i,1,k*2+1) s+='1';
		dfs(n-(2*k+1),x-f[n-1]);
	}
}
string send(int Taskid,int n,int K,ll x){
	k=K;
	s=""; 
	if(x<f[n])dfs(n,x);
	else{
		x-=f[n];
		For(i,1,k*2){
			s+='1';
			if(i%(k*2+1)==0)continue;
			if(x<f[n-i]){
				dfs(n-i,x);
				break;
			}
			x-=f[n-i];
		}
	}
//	assert(s.size()==n);
	return s;
}

int c0,c1;
ll res;

void add0(){
	res+=0;
	n-=1;
}
void add1(){
	res+=f[n-1];
	n-=k*2+1;
}

string cuts(string s,int o){
	string t;
	for(auto c:s){
		if(c=='0')t+=c;
		else{
			if(o)--o;
			else t+=c;
		}
	}
	return t;
}

ll receive(int Taskid,int K,const string&S){
	init_dp(K);
	k=K; s=S; c0=c1=0;
	n=s.size(); res=0;
	int sum=0;
	for(auto c:s)sum+=(c&1);
	sum%=(k*2+1);
	if(sum){
	//	cout<<"rsum "<<sum<<endl;
		res+=f[n];
		For(i,1,k*2){
			if(i%(k*2+1)==0)continue;
			if(sum%(k*2+1)==i%(k*2+1)){
				s=cuts(s,i);
				break;
			}
			res+=f[n-i];
		}
	}
	
	n=s.size();
	For(i,0,(int)s.size()-1){
		if(s[i]=='1'){
			++c1;
			if(c1%(k*2+1)==k+1){
				For(_,1,c0)add0(); c0=0;
				add1();
			}
		}else{
			++c0;
		}
	}
//	cout<<"c1 "<<c1<<" "<<c1%(k*2+1)<<endl;
	For(_,1,c0)add0();
	return res;
}