#include<bits/stdc++.h> using namespace std; int a,b,c[100005],d[100005],e,h; bool f[100000005]; void g(){ cin>>a>>b>>d[1]; for(int i=1;i<=a;++i){ c[i]=d[i]%4; d[i+1]=(d[i]*6807+2831)%201701; } } int main(){ g(); for(int i=1;i<=a-b+1;i++){ for(int j=1;j<=b;j++)h=h*4+c[i+j-1]; if(f[h]==0) e++; } cout<<e<<endl; return 0; }