#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int k,h,u,l,ans=1;
string a[N];
bool f;
int main(){
    cin >> k >> h >> u;
    if (k==h){
    	cout << 1;
		return 0; 
	} 
	if (k<h){
		cout << 0;
		return 0;
	}
    for (int i = 1;i <= k;i++){
        int y=l%4;
        if (y==0) a[i]="A";
        if (y==1) a[i]="T";
        if (y==2) a[i]="C";
        if (y==0) a[i]="G";
        l=(l*6807+2831)%201701;
    }
    for (int i =h;i <= k;i++){
    	for (int j= 1;j <= h;j++){
    		a[i]= a[i-j]+a[i];
		}
    }
    for (int i = h+1;i <= k;i++){
    	f=true;
    	for (int j = h;j < i;j++){
    		if (a[j]==a[i]) f=false;
		}
		if (f) ans++;
	} 
	cout << ans;
}