// Artur Kraska, II UWr

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <cmath>
#include <list>
#include <set>
#include <map>

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

#define forr(i, n)                  for(int i=0; i<n; i++)
#define FOREACH(iter, coll)         for(typeof(coll.begin()) iter = coll.begin(); iter != coll.end(); ++iter)
#define FOREACHR(iter, coll)        for(typeof(coll.rbegin()) iter = coll.rbegin(); iter != coll.rend(); ++iter)
#define lbound(P,R,PRED)            ({typeof(P) X=P,RRR=(R), PPP = P; while(PPP<RRR) {X = (PPP+(RRR-PPP)/2); if(PRED) RRR = X; else PPP = X+1;} PPP;})
#define testy()                     int _tests; scanf("%d", &_tests); FOR(_test, 1, _tests)
#define CLEAR(tab)                  memset(tab, 0, sizeof(tab))
#define CONTAIN(el, coll)           (coll.find(el) != coll.end())
#define FOR(i, a, b)                for(int i=a; i<=b; i++)
#define FORD(i, a, b)               for(int i=a; i>=b; i--)
#define MP                          make_pair
#define PB                          push_back
#define deb(X)                      X;

#define M 1000000007
#define INF 1000000007

using namespace std;

long long N, NR;
long long n, m;
long long res = 0;

/***** KMP *****/

#define KMP_LIMIT 10000000

long long pocz, kon;
int p[KMP_LIMIT+7];

#define wz(i) (i >= 0 && i < m ? SignalAt(i+1) : -1)

int fun(int nr)
{
    res++;
//    printf("wzorzec wystapil na pozycji %d\n", nr);
}

void pre(int t[])
{
    t[0] = -1;
    int poz = -1;
    //wz[0] = SignalAt(1);
    for(int i=1; i < m; i++)
    {
        //wz[i] = SignalAt(i+1);
        while(poz != -1 && wz(poz+1) != wz(i))   poz = t[poz];
        if(wz(poz+1) == wz(i))   poz++;
        t[i] = poz;
//        printf("t[%d] = %d\n", i, poz);
    }
}

void kmp(int t[])
{
    int poz = -1;
    long long a;
    for(int i=pocz; i < kon; i++)
    {
        a = SeqAt(i+1);
        while(poz != -1 && wz(poz+1) != a)   poz = t[poz];
        if(wz(poz+1) == a)   poz++;
//        printf("na pozycji %d jest %d\n", i, poz);
        if(poz != -1 && wz(poz+1) == -1)
            fun(i-poz);
    }
}

/***** HASHOWANIE *****/

#define ILE_H 3

#define seqAt(i) SeqAt(i+1)
#define signalAt(i) SignalAt(i+1)

long long P[] = {2000707019, 2000707103, 2000707207, 2000707307, 2000707409}, POT[ILE_H];
long long X[] = {1000707017, 1000707107, 1000707229, 1000707343, 1000707419}, O[ILE_H];

long long pot(long long a, long long n, long long mod)
{
    if(n == 0)
        return 1;
    long long p = pot(a, n/2, mod);
    p = (p*p)%mod;
    if(n%2 == 1)
        p = (p*a)%mod;
    return p;
}

pair <long long, long long> euklid(long long a, long long b)
{
    if(b == 0)   return make_pair(1, 0);
    pair <long long, long long> p = euklid(b, a%b);
    return make_pair(p.second, p.first - p.second * (a/b));
}

long long odwr(long long a, long long mod)
{
    long long e = euklid(a, mod).first;
    return (e < 0 ? mod-((-e) % mod) : (e % mod));
}

void init()
{
    forr(i, ILE_H)
    {
        POT[i] = pot(X[i], m, P[i]);
        O[i] = odwr(POT[i], P[i]);
    }
}

struct hasz
{
    long long t[ILE_H];
    int dl;
};
hasz hs, hm, h, hh, haszm[1007];

int poczm[1007];

void dohaszuj(hasz &h, long long elem)
{
    forr(i, ILE_H)
    {
        h.t[i] = ((h.t[i]*X[i])%P[i] + elem) % P[i];
    }
    h.dl++;
}

void dohaszuj_hasz(hasz &h, hasz h2)
{
    forr(i, ILE_H)
    {
        h.t[i] = ((h.t[i]*pot(X[i], h2.dl, P[i]))%P[i] + h2.t[i]) % P[i];
    }
    h.dl += h2.dl;
}

void odhaszuj(hasz &h, long long elem)
{
    forr(i, ILE_H)
    {
        h.t[i] = (h.t[i] + elem*(P[i] - POT[i])) % P[i];
    }
    h.dl--;
}

void putHasz(int nr, hasz h)
{
    forr(i, ILE_H)
    {
        PutLL(nr, h.t[i]);
    }
    PutInt(nr, h.dl);
}

hasz getHasz(int nr)
{
    hasz h;
    forr(i, ILE_H)
        h.t[i] = GetLL(nr);
    h.dl = GetInt(nr);
    return h;
}

bool porownaj(hasz h1, hasz h2)
{
    forr(i, ILE_H)
        if(h1.t[i] != h2.t[i])
            return false;
    return h1.dl == h2.dl;
}

void wyswietl(hasz h)
{
    cout << "   hash: " << h.t[0] << ", dl: " << h.dl << endl;
}

int main()
{
    n = SeqLength();
    m = SignalLength();
    N = NumberOfNodes();
    NR = MyNodeId();

    if(m <= KMP_LIMIT) // KMP
    {
        pocz = (n-m+1)*NR/N;
        kon = (n-m+1)*(NR+1)/N + m-1;

        pre(p);
        kmp(p);
    }
    else // HASHOWANIE
    {
        init();

        //forr(i, 10)
        //    cout << "pot: " << pot(2, i, 100) << endl;

        FOR(i, 0, N)
        {
            poczm[i] = n*i/N;
        }

        // hashuj fragment S i M
        pocz = m*NR/N;
        kon = m*(NR+1)/N;
        FOR(i, pocz, kon-1)
        {
            if(i < 0 || i >= m)
                return i;
            dohaszuj(hs, signalAt(i));
        }

        //cout << "hs dla [" << pocz << ", " << kon << "] - ";
        //wyswietl(hs);

        pocz = n*NR/N;
        kon = n*(NR+1)/N;
        FOR(i, pocz, kon-1)
            dohaszuj(hm, seqAt(i));

        //cout << "hm dla [" << pocz << ", " << kon << "] - ";
        //wyswietl(hm);

        // pozbieraj w 0 i rozeslij
        if(NR == 0)
        {
            haszm[0] = hm;
            FOR(i, 1, N-1)
            {
                Receive(i);
                hh = getHasz(i);
                dohaszuj_hasz(hs, hh);
                haszm[i] = getHasz(i);
            }

            //cout << "hs - ";
            //wyswietl(hs);
            /*
            forr(j, N)
            {
                cout << "poczm[" << j << "] = " << poczm[j] << ", hm[" << j << "] = ";
                wyswietl(haszm[j]);
            }
            */

            FOR(i, 1, N-1)
            {
                putHasz(i, hs);
                forr(j, N)
                    putHasz(i, haszm[j]);
                Send(i);
            }
        }
        else
        {
            putHasz(0, hs);
            putHasz(0, hm);
            Send(0);

            Receive(0);
            hs = getHasz(0);
            forr(i, N)
                haszm[i] = getHasz(0);
        }

        // tutaj ka¿dy ma poprawne hs i haszm[]

        pocz = (n-m+1)*NR/N;
        kon = (n-m+1)*(NR+1)/N;

        long long kons = pocz + m;
        int im = 0;
        while(poczm[im] < pocz)
            im++;

        for(int i = pocz; i < kons;)
        {
            if(i == poczm[im] && poczm[im+1] <= kons)
            {
                //cout << "dohashowuje ";
                //wyswietl(haszm[im]);
                dohaszuj_hasz(h, haszm[im]);
                i += haszm[im].dl;
                im++;
            }
            else
            {
                //cout << "dohashowuje " << seqAt(i) << endl;
                dohaszuj(h, seqAt(i));
                i++;
            }
        }

        FOR(i, pocz, kon-1)
        {
            if(porownaj(h, hs))
                res++;
            //cout << " hasz o poczatku w " << i << " - ";
            //wyswietl(h);
            if(i+m >= n)
                break;
            dohaszuj(h, seqAt(i+m));
            odhaszuj(h, seqAt(i));
        }

    }

    if(NR == 0)
    {
        FOR(i, 1, N-1)
        {
            Receive(i);
            long long a = GetLL(i);
            res += a;
        }

        printf("%lld\n", res);
    }
    else
    {
        PutLL(0, res);
        Send(0);
    }

    return 0;
}