#include<bits/stdc++.h>
using namespace std;
char in[100], out[100];

map<long long int, long long int> A, B;

long long int k, n, chk[30];

long long int g(long long int c){
    long long int ans=0;
    int i;
    if(c<0) return 0;
    if(c==0) return 1;
    if(chk[c]>0) return chk[c];
    for(i=1;i<=c;i++) ans = (ans + g(c-i))%1000000007;
    return chk[c] = ans;
}

long long int f(long long int c){
    long long int ans=0;
    int i, j;
    if(c==0) return 1;
    if(c<=k) return chk[c];
    if(B[c]==1) return A[c];
    for(i=1;i<=k;i++){
        for(j=0;j<i;j++){
            if(c/2-j>=0 and (c+1)/2-i+j >= 0){
                ans =(ans+f(c/2-j)*f((c+1)/2-i+j))%1000000007;
            }
        }
    }
    B[c]=1;
    return A[c] = ans;
}

int main(){
	for(int I=1;I<=20; I++){
		A.clear();
		B.clear();
		for(int i=0;i<30;i++) chk[i] = 0;
	    //scanf("%lld %lld", &n, &k);
	    if(I<5){
	    	k = 2;
	    	n = I;
		}else if(I==20){
			k = 2;
			n = 100000;
		}else{
			k = 2;
			n = (rand()*1000+rand())%100000+1;
		}
		sprintf(in,".%d.in",I);
		freopen(in,"w",stdout);		
	    printf("%lld %lld\n", n, k);
		g(k);
		sprintf(out,".%d.out",I);
		freopen(out,"w",stdout);
	    printf("%lld\n", f(n));
	}
}