#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<=100)return 0;
	ll res=1;
	if(add(res,f[n]))return 1;
//	For(i,k+1,(2*k))if(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; init_dp(K);
	s=""; 
	dfs(n,x);
//	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;
}

ll receive(int Taskid,int K,const string&S){
	init_dp(K);
	k=K; s=S; c0=c1=0;
	n=s.size(); res=0;
	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;
		}
	}
	For(_,1,c0)add0();
	return res;
}