#include <bits/stdc++.h>
using namespace std;

string str="ATCG",a,c;
map<string,int> m;
int n,k,r;

int main()
{
	cin >> n >> k >> r;
	for (int i=1;i<=n;i++)
	{
		a+=str[r%4];
		r=(r*6807+2831)%201701;
	}

	for(int i=1;i<=k;i++)
		c+=a[i-1];

	m[c]=1;
	for (int i=k+1;i<=n;i++)
	{
		c+=a[i-1];
		c.erase(0,1);
		if (!m[c])
			m[c]=1;
	}
	cout << m.size() << endl;
	return 0;
}


/**************************************************************
	Problem: 1552
	User: admin
	Language: C++
	Result: Accepted
	Time:54 ms
	Memory:2080 kb
****************************************************************/