## Editorial for Tung đồng xu

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

const fi='';
fo='';
maxn=10000;
base=1000000000;
dg=9;
type bignum=array[0..340] of longint;
var n,k:longint;
re,p:bignum;
g:array[0..maxn] of bignum;

procedure rf;
begin
end;

procedure plus(var a,b:bignum);
var i,mem,max:Longint;
begin
if b[0]>a[0] then max:=b[0] else max:=a[0];
mem:=0;
for i:=1 to max do
begin
a[i]:=a[i]+b[i]+mem;
if a[i]<base then mem:=0
else
begin
mem:=1;
a[i]:=a[i]-base;
end;
end;
if mem>0 then
begin
inc(max);
a[max]:=1;
end;
a[0]:=max;
end;

procedure minus(var a,b,c:bignum);
var i,mem:longint;
begin
mem:=0;
for i:=1 to b[0] do
begin
a[i]:=b[i]-c[i]-mem;
if a[i]>0 then mem:=0
else
begin
a[i]:=a[i]+base;
mem:=1;
end;
end;
a[0]:=b[0];
while (a[0]>1) and (a[a[0]]=0) do dec(a[0]);
end;

procedure mul(var a:bignum);
var i,mem:longint;
begin
mem:=0;
for i:=1 to a[0] do
begin
a[i]:=a[i] shl 1+mem;
if a[i]<base then mem:=0
else
begin
mem:=1;
a[i]:=a[i]-base;
end;
end;
if mem>0 then
begin
inc(a[0]);
a[a[0]]:=1;
end;
end;

procedure pr;
var i,j:longint;
begin
p[0]:=1; p[1]:=1;
g[0,0]:=1; g[0,1]:=1; re[0]:=1;
for i:=1 to k-1 do
begin
mul(p);
for j:=0 to p[0] do g[i,j]:=p[j];
end;
for i:=k to n do
begin
mul(p);
mul(re);
if i>k then plus(re,g[i-k-1])
else re[1]:=1;
if i<=n-k-1 then minus(g[i],p,re);
end;
end;

procedure wf;
var i,j,l:longint; s:string;
begin
for i:=re[0] downto 1 do
begin
if i<re[0] then
begin
str(re[i],s);
l:=length(s);
for j:=l+1 to dg do write(0);
end;
write(re[i]);
end;
end;

begin
assign(input,fi); reset(input);
assign(output,fo); rewrite(output);
rf;
pr;
wf;
close(input); close(output);
end.


#include <bits/stdc++.h>
const int MOD = 100000000;
using namespace std;
typedef vector<int> big;

int n, k;
big F[10005];

big operator + (const big &a, const big &b) {
big c; int carry = 0;
for(int i = 0; i < a.size() || i < b.size(); i++) {
if (i < a.size()) carry += a[i];
if (i < b.size()) carry += b[i];
c.push_back(carry % MOD);
carry /= MOD;
}
if (carry) c.push_back(carry);
return c;
}

big operator - (const big &a, const big &b) {
big c; int borrow = 0, s;
for(int i = 0; i < a.size(); i++) {
s = a[i] - borrow;
if (i < b.size()) s -= b[i];
if (s < 0) {
s += MOD;
borrow = 1;
}
else
borrow = 0;
c.push_back(s);
}
while (!c.empty() && c[c.size() - 1] == 0) c.pop_back();
return c;

}

void print(big a) {
printf("%d", a[a.size() - 1]);
for(int i = a.size() - 2; i >= 0; i--)
printf("%08d", a[i]);
printf("\n");
}

int main() {
scanf("%d %d", &n, &k);
F[0].push_back(1);
big prev; prev.push_back(1);
big POW; POW.push_back(1);
for(int i = 1; i <= n + 1; i++) {
F[i] = prev;
prev = prev + F[i];
if (i >= k)
prev = prev - F[i - k];
if (i <= n)
POW = POW + POW;
}
print(POW - F[n + 1]);
return 0;
}


#### Code mẫu của RR

{$R+,Q+} {$Mode objFPC}
uses math;
const
FINP='';
FOUT='';
MAXN=10000;
oo=100000000;
type
big=array[0..400] of longint;
var
f1,f2:text;
n,k:longint;
d:array[-1..MAXN] of big;
lt2:big;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1); close(f2);
end;
procedure solve;
var
scs,nho,i,t:longint;
temp:int64;
begin
d[k][0]:=1; d[k][1]:=1;
lt2[0]:=1; lt2[1]:=1;
for i:=k+1 to n do
begin
scs:=max(max(d[i-1,0],d[i-k-1,0]),lt2[0]);
nho:=0; t:=i-k-1;
for scs:=1 to scs do
begin
temp:=d[i-1,scs]<<1-d[t,scs];
temp+=int64(lt2[scs])+nho;
if (temp<oo) and (temp>=0) then begin nho:=0; d[i,scs]:=temp; end
else if temp>=0 then begin nho:=temp div oo; d[i,scs]:=temp mod oo; end
else begin nho:=-1; d[i,scs]:=temp+oo; end;
end;
if nho>0 then
begin inc(scs); d[i,scs]:=nho; end;
d[i,0]:=scs;
scs:=lt2[0]; nho:=0;
for scs:=1 to scs do
begin
lt2[scs]:=lt2[scs]<<1+nho;
if lt2[scs]<oo then nho:=0 else begin lt2[scs]-=oo; nho:=1; end;
end;
if nho>0 then begin inc(lt2[0]); lt2[lt2[0]]:=nho; end;
end;
end;
procedure ans;
var
i,ii:longint;
s:string[10];
begin
write(f2,d[n,d[n,0]]);
for i:=d[n,0]-1 downto 1 do
begin
str(d[n,i],s);
for ii:=8-length(s) downto 1 do write(f2,'0');
write(f2,s);
end;
writeln(f2);
end;
begin
openF;
solve;
ans;
closeF;
end.


#### Code mẫu của hieult

#include <cstdio>
#include <iostream>
//#include <conio.h>
#define base 1000000000

using namespace std;

struct solon
{
int so;
long long a[400];
};

int n,k;
solon F[11111],t;

solon tong (solon A,solon B)
{
int du = 0;
solon C;
if(A.so<B.so)
{
C = A;
A = B;
B = C;
}
for(int i = B.so+1;i<=A.so;i++) B.a[i] = 0;
C.so = A.so;
for(int i = 1;i<=A.so;i++)
{
C.a[i] = (A.a[i]+B.a[i]+du)%base;
du = (A.a[i]+B.a[i]+du)/base;
}
if(du>0) {C.so++; C.a[C.so] = du;}
return C;
}

solon tichnho(solon A,long long k,int chuso)
{
solon C;
long long du = 0;
C.so = A.so+chuso;
for(int i = 1;i<=chuso;i++)
C.a[i] = 0;
for(int i = chuso+1;i<=chuso+A.so;i++)
{
C.a[i] = (A.a[i-chuso]*k+du)%base;
du = (A.a[i-chuso]*k+du)/base;
}
if(du>0) {C.so++; C.a[C.so] = du;}
return C;
}

solon tich2(solon A){
solon C;
int du = 0;
C.so = A.so;
for(int i = 1;i<=A.so;i++){
C.a[i] = (A.a[i]*2+du);
if(C.a[i]>=base){
C.a[i]-=base;
du = 1;
}
else du = 0;
}
if(du>0) {C.so++; C.a[C.so] = du;}
return C;
}

solon tich(solon A,solon B)
{
solon C;
C.so = 1; C.a[1] = 0;
for(int i = 1;i<=B.so;i++)
{
C = tong(C,tichnho(A,B.a[i],i-1));
}
return C;
}

void print(solon A)
{
printf("%lld",A.a[A.so]);
for(int i = A.so-1;i>=1;i--)
printf("%09lld",A.a[i]);
}

solon hieu(solon A,solon B){
solon C; C.so = A.so;
for(int i = B.so+1;i<=A.so;i++)
B.a[i] = 0;
int du = 0;
for(int i = 1;i<=A.so;i++){
C.a[i] = A.a[i]-B.a[i]-du;
if(C.a[i]<0){
C.a[i]+=base;
du = 1;
}
else du = 0;
}
while(C.a[C.so]==0) C.so--;
if(C.so==0) C.so = 1;
return C;
}

solon Hieu(solon A,solon B){
solon C; C.so = A.so;
int du = 0;
for(int i = 1;i<=A.so;i++){
if(i>B.so) B.a[i] = 0;
if(i>t.so) t.a[i] = 0;
C.a[i] = A.a[i]-B.a[i]+t.a[i]-du;
if(C.a[i]<0){
C.a[i]+=base;
du = 1;
}
else if(C.a[i]>=base){
C.a[i]-=base;
du = -1;
}
else du = 0;
}
if(du == -1) C.a[++C.so] = 1;
while(C.a[C.so]==0) C.so--;
if(C.so==0) C.so = 1;
return C;
}

int main()
{
scanf("%d %d",&n,&k);
t.so = 1; t.a[1] = 1;
for(int i = 0;i<=n;i++){
if(i<k){
F[i].so = 1 ;
F[i].a[1] = 0;
}
else if(i==k) {
F[i].so = 1;
F[i].a[1] = 1;
}
else{
F[i] = Hieu(tich2(F[i-1]),F[i-k-1]);
t = tich2(t);
}
}
print(F[n]);
//  getch();
}


#### Code mẫu của khuc_tuan

import java.util.*;
import java.math.*;

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
BigInteger[] F = new BigInteger[n+1];
F[0] = BigInteger.ONE;
BigInteger total = BigInteger.ONE;
for(int i=1;i<=n;++i) {

F[i] = total;

if(i>=k) total = total.subtract(F[i-k]);
}
BigInteger res = BigInteger.ONE;
for(int i=0;i<n;++i) res = res.multiply(BigInteger.valueOf(2));
System.out.println(res.subtract(F[n]));
}
}