#include <bits/stdc++.h> using namespace std; int n,k,a[100005],r[100005],s; int h[100000005]; void init() { cin>>n>>k>>r[1]; for(int i=1; i<=n; ++i) { a[i]=r[i]%4; r[i+1]=(r[i]*6807+2831)%201701; } } int main() { init(); for(int i=1; i<=n-k+1; i++) { int sum=0; for(int j=1; j<=k; j++)sum=sum*10+a[i+j-1]; if(!h[sum])h[sum]++,s++; } cout<<s<<endl; return 0; }