#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>		//UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>		//do setprecision
#include <ctime>
#include <complex>
using namespace std;

#include "message.h"
#include "poszukiwania.h"

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;

const int p = 70032301;
const int q = 1000000007;
const int odwp = 108247208;
const int treshold = 1e6;

int N;

inline int pow(int a, int b)
{
	int res = 1;
	while(b)
	{
		if(b & 1)
			res = (res*(LL)a) % q;
		a = (a*(LL)a) % q;
		b /= 2;
	}

	return res;
}

inline void policzHasz(int I, int nr, int &hasz)
{
	hasz = 0;
	if(N < I || I == 1)
	{
		// kazdy sobie sam wyliczy
		FORD(i,N,0) hasz = (hasz * (LL)p +  SignalAt(i+1)) % q;
	}
	else
	{
		// troche zabawy
		int d;
		if(N%I == 0) d = N/I;
		else d = (N-1)/(I-1);
		// policz p^d
		int pd = pow(p,d);
		// wylicz swoj kawalek
		int b = nr*d, e = nr == I-1 ? N : (nr+1)*d;
		FORD(i,e,b) hasz = (hasz * (LL)p +  SignalAt(i+1)) % q;
		// poczekaj na nastepna jesli nie jestes ostatnia
		int nast = 0;
		if(nr < I-1)
		{
			Receive(nr+1);
			nast = GetInt(nr+1);
			hasz = (hasz+nast*(LL)pd) % q;
		}
		if(nr)	// przeslij do poprzednika
		{
			PutInt(nr-1, hasz);
			Send(nr-1);
		}
		else	// wyslij ostateczny hasz do pozostalych jesli jestes 0
		{
			FOR(i,1,I)
			{
				PutInt(i, hasz);
				Send(i);
			}
		}
		if(nr)	// odbierz ostateczny hasz
		{
			Receive(0);
			hasz = GetInt(0);
		}
	}

	//printf("hasz:%d\n", hasz);
}

int *hasze;
int S;

inline void policzText(int I, int nr, int M)
{
	if(M < I || I == 1)
	{
		// instancja 0 zrobi wszystko
		if(!nr)
		{
			hasze = new int[M+1];
			hasze[M] = 0;
			FORD(i,M,0) hasze[i] = (hasze[i+1]*(LL)p + SeqAt(i+1)) % q;
		}
	}
	else
	{
		// troche zabawy
		int d;
		if(M%I == 0) d = M/I;
		else d = (M-1)/(I-1);
		// policz p^d
		int pd = pow(p,d);
		int b = nr*d, e = nr == I-1 ? M : (nr+1)*d;
		hasze = new int[e-b+1];
		hasze[e-b] = 0;
		FORD(i,e,b) hasze[i-b] = (hasze[i-b+1]*(LL)p + SeqAt(i+1)) % q;
		
		// poczekaj na nastepna jesli nie jestes ostatnia
		int nast = 0;
		if(nr < I-1)
		{
			Receive(nr+1);
			nast = GetInt(nr+1);
		}
		hasze[0] = (hasze[0] + nast*(LL)pd) % q;
		if(nr)
		{
			// przeslij swoja wartosc poprzedniemu
			PutInt(nr-1, hasze[0]);
			Send(nr-1);
		}
		// uzupelnij reszte - po przeslaniu!
		if(nast > 0)
		{
			FORD(i,e,b+1)
			{
				nast = (nast*(LL)p) % q;
				hasze[i-b] = (hasze[i-b] + nast) % q;
			}
		}

		//printf("hasze instancji %d\n", nr);
		//FOR(i,b,e) printf("%d ", hasze[i-b]);
		//printf("\n");
	}
}

const int losowania = 7;

int los[losowania];
inline bool spr(int b)
{
	//printf("losuje liczbe b:%d N:%d\n", b, N);
	REP(i,losowania)
	{
		//printf("wylosowal %d\n", pos);
		int x = SignalAt(los[i]);
		int y = SeqAt(b+los[i]);
		if(x != y) return 0;
	}

	return 1;
}

inline void policzWyst(int I, int nr, int M, int hasz)
{
	int res = 0;
	int ileB = M-N+1;
	int pn = pow(p,N);

	if(M < I || I == 1)
	{
		// instancja 0 zrobi wszystko
		if(!nr)
		{
			REP(i,ileB)
			{
				if(hasz == (hasze[i]-(hasze[i+N]*(LL)pn)%q+q) % q) res += spr(i);
			}
		}
	}
	else
	{
		int d;
		if(M%I == 0) d = M/I;
		else d = (M-1)/(I-1);
		int b = nr*d, e = nr == I-1 ? M : (nr+1)*d;
		//printf("%d zaczyna liczyc b:%d e:%d d:%d\n", nr, b, e, d);
		// wyznacz od kogo odbierasz pytanie
		vector < int > odbierasz;
		REP(i,nr)
			if(i*d+N >= b)
			{
				if(i*d+N > e) break;
				else if(i*d+N < e)
				{
					odbierasz.PB(i);
				}
				else if(nr == I-1)
				{
					odbierasz.PB(i);
				}
			}
		int wysylasz = -1;
		if(b < ileB)
		{
			// pierwsze co, to zapytaj sie o sume za koncem
			wysylasz = min((b+N)/d, I-1);
			if(wysylasz > nr)
			{
				//printf("%d wysyla do %d pytanie o %d\n", nr, wysylasz, b+N);
				// wyslij wiadomosc
				PutInt(wysylasz, b+N);
				Send(wysylasz);
			}
		}
		// spr czy musisz czekac na pytanie
		if(!odbierasz.empty())
		{
			FORD(i,odbierasz.size(),0)
			{
				Receive(odbierasz[i]);
				int v = GetInt(odbierasz[i]);
				//printf("%d odebral od %d pytanie o %d\n", nr, odbierasz[i], v);
				// daj wartosc z pozycji v
				//assert(v >= b && v <= e);
				PutInt(odbierasz[i], hasze[v-b]);
				//printf("%d przygotowal odpowiedz dla %d, b:%d, v:%d, hasze[v-b]:%d\n", nr, odbierasz[i], b, v, hasze[v-b]);
				Send(odbierasz[i]);
			}
		}
		if(b < ileB)
		{
			//printf("%d bedzie liczyl, odbiera wiadomosc od %d\n", nr, wysylasz);
			// wreszcie bedziesz liczyl, tylko odbierz sume, jesli o nia pytales
			int sum;
			if(wysylasz > nr)
			{
				// wyslales wiadomosc, czekasz na odbior
				Receive(wysylasz);
				sum = GetInt(wysylasz);
				//printf("%d odebral odpowiedz od %d wynik %d\n", nr, wysylasz, sum);
			}
			else sum = hasze[N];

			int pom = min(e, ileB);
			//printf("%d przygotowuje sie do petli od %d do %d\n", nr, b, pom);
			FOR(i,b,pom-1)
			{
				//printf("%d rozpatruje sume %d\n", nr, sum);
				if(hasz == (hasze[i-b]-(sum*(LL)pn)%q+q) % q) res += spr(i);
				sum = (sum-SeqAt(i+N+1)+q) % q;
				sum = (sum*(LL)odwp) % q;
			}
			// jeszcze jedno sprawdzenie na koncu trzeba zrobic
			if(hasz == (hasze[pom-b-1]-(sum*(LL)pn)%q+q) % q) res += spr(pom-1);
		}
		// przeslij wiadomosc do 0
		if(nr)
		{
			//printf("%d wysyla res:%d do 0\n", nr, res);
			PutInt(0, res);
			Send(0);
		}
		else
		{
			FOR(i,1,I)
			{
				Receive(i);
				int dostal = GetInt(i);;
				res += dostal;
				//printf("0 odebral res:%d od %d\n", dostal, i);
			}
		}
	}

	if(!nr)
	{
		// wypisz wynik jesli jestes instancja 0
		printf("%d\n", res);
	}
}

int main()
{
	srand((int)time(NULL));
	int I = NumberOfNodes();
	int nr = MyNodeId();
	N = SignalLength();
	int M =  SeqLength();
	REP(i,losowania) los[i] = rand()%N + 1;
	// liczenie haszu dla wzorca
	int hasz;
	policzHasz(I, nr, hasz);
	policzText(I, nr, M);
	policzWyst(I, nr, M, hasz);

	//delete[] hasze;

	return 0;
}