#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <cstdio>
#include <vector>
#include <utility>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include "message.h"
#include "poszukiwania.h"

#define ST first
#define ND second
#define MP make_pair
#define PB push_back
#define QI queue <int>
#define VI vector <int>
#define PII pair <int,int>
#define SZ(x) (int)(x).size()
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
#define SYNC ios_base::sync_with_stdio(0)
#define MAX(a,b) ((a) > (b)) ? a : b

using namespace std;

typedef long long LL;
typedef long double LD;
typedef unsigned int UI;
typedef unsigned long long ULL;

const LL MOD = 1000000000000037LL;
const LL PRIME = 1e9 + 7;

int a, b, c, d, e, f;
LL sumHash, signalHash, wynik, ilezgodnych, hashh, poczatek, koniec, firstSeq;
LL primePow, primePow2, primePow3, n, m, maszyny, podzial;

vector <LL> Start;

LL Multiply(LL,LL,LL);

int main()
{
  n = (int)SignalLength();
  m = (int)SeqLength();
  maszyny = NumberOfNodes();
  primePow = primePow2 = primePow3 = 1;
  podzial = (n + maszyny - 1) / maszyny;
  
  for(int i = 1; i <= podzial; i++)
  {
    primePow = Multiply(primePow, PRIME, MOD);
  }
  for(int i = 1; i <= n; i++)
  {
    primePow2 = Multiply(primePow2, PRIME, MOD);
  }
  for(int i = 1; i <= n - podzial; i++)
  {
    primePow3 = Multiply(primePow3, PRIME, MOD);
  }
  
  //obliczamy hasza dla wzorca
  poczatek = podzial * MyNodeId() + 1;
  koniec = min(poczatek + podzial - 1, n);
  
  for(int i = poczatek; i <= koniec; i++)
  {
    sumHash = Multiply(sumHash, PRIME, MOD);
    sumHash = (sumHash + SignalAt(i)) % MOD;  
  }
  PutLL(0, sumHash);
  Send(0);
  if(MyNodeId() == 0)
  {
    for(int i = 0; i < maszyny; i++)
    {
      signalHash = Multiply(signalHash, primePow, MOD);
      Receive(i);
      signalHash = (signalHash + GetLL(i)) % MOD;
    }
    for(int i = 0; i < maszyny; i++)
    {
      PutLL(i, signalHash);
      Send(i);
    }
  }
  Receive(0);
  signalHash = GetLL(0);
  
  
  //obliczamy pierwszego hasza dla ciagu
  sumHash = 0;
  for(int i = poczatek; i <= koniec; i++)
  {
    sumHash = Multiply(sumHash, PRIME, MOD);
    sumHash = (sumHash + SeqAt(i)) % MOD;  
  }
  PutLL(0, sumHash);
  Send(0);
  if(MyNodeId() == 0)
  {
    for(int i = 0; i < maszyny; i++)
    {
      firstSeq = Multiply(firstSeq, primePow, MOD);
      Receive(i);
      firstSeq = (signalHash + GetLL(i)) % MOD;
    }
    Start.PB(firstSeq);
  }
  
  //obliczamy kolejne hasze startowe
  if(n > podzial)
  {
    podzial = (m - n + maszyny) / maszyny;
    
    poczatek = (podzial - 1) * MyNodeId() + 1;
    koniec = min(poczatek + podzial - 1, m);
    hashh = 0;
    for(int i = poczatek; i <= koniec; i++)
    {
      hashh = Multiply(hashh, PRIME, MOD);
      hashh = (hashh + SignalAt(i)) % MOD;
    }
    PutLL(0, hashh);
    Send(0);
    
    poczatek = poczatek + n;
    koniec = min(poczatek + podzial - 1, m);
    hashh = 0;
    for(int i = poczatek; i <= koniec; i++)
    {
      hashh = Multiply(hashh, PRIME, MOD);
      hashh = (hashh + SignalAt(i)) % MOD;
    }
    PutLL(0, hashh);
    Send(0);
  }
  else
  {
    podzial = (m - n + maszyny) / maszyny;
    poczatek = podzial * MyNodeId() + 1;
    koniec = poczatek + n - 1;
    hashh = 0;
    for(int i = poczatek; i <= koniec; i++)
    {
      hashh = Multiply(hashh, PRIME, MOD);
      hashh = (hashh + SignalAt(i)) % MOD;
    }
    PutLL(0, hashh);
    Send(0);
  }
  
  
  if(MyNodeId() == 0)
  {
    if(n > podzial)
    {
      hashh = firstSeq;
      for(int i = 1; i < maszyny; i++)
      {
        Receive(i);
        LL pocz = GetLL(i);
        pocz = Multiply(pocz, primePow3, MOD);
        LL kon = GetLL(i);
        hashh = (hashh - pocz + MOD) % MOD;
        hashh = Multiply(hashh, primePow, MOD);
        hashh = (hashh + kon) % MOD;
        Start.PB(hashh);
      }
    }
    else
    {
      for(int i = 1; i < maszyny; i++)
      {
        Receive(i);
        Start.PB(GetLL(i));
      }
    }
    for(int i = 0; i < maszyny; i++)
    {
      PutLL(i, Start[i - 1]);
      Send(i);
    }
  }
  
  //obliczamy hasze kolejny podslow
  Receive(0);
  hashh = GetLL(0);
  ilezgodnych += (hashh == signalHash);
  podzial = (m - n + maszyny) / maszyny;
  
  poczatek = podzial * MyNodeId() + 1;
  koniec = min(poczatek + podzial - 1, n);
  for(int i = poczatek; i <= koniec - 1; i++)
  {
    LL val = Multiply(SeqAt((LL)(i)), primePow2, MOD);
    hashh = (hashh - val + MOD) % MOD;
    hashh = Multiply(hashh, PRIME, MOD);
    hashh = (hashh + SeqAt((LL)(i + podzial))) % MOD;
    ilezgodnych += (hashh == signalHash);
  }
  PutLL(0, ilezgodnych);
  Send(0);
  
  if(MyNodeId() == 0)
  {
    for(int i = 0; i < maszyny; i++)
    {
      Receive(i);
      wynik += GetLL(i);
    }
    printf("%lld\n", wynik);
  }
}

LL Multiply(LL A, LL B, LL M)
{
  LL res = 0;
  do
  {
    if(A & 1)
    {
      res += B;
      res %= M;
    }
    B += B;
    B %+ M;
  }
  while(A >>= 1);
  return res;
}