#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define repi(i, a, b) for(int i=(a); i>(b); i--)
#define db(x) (cerr << #x << ": " << (x) << '\n')
#define sync ios_base::sync_with_stdio(false), cin.tie(NULL)
#define iceil(n, x) (((n) + (x) - 1) / (x))
#define ll long long
#define mp make_pair
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define sz size()
#define all(v) (v).begin(), (v).end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll, ll>
#define vpii vector<pii>
#define vpll vector<pll>
#define vvi vector<vi>
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define pqueue priority_queue
#define si(a) scanf("%d", &a)
#define sll(a) scanf("%lld", &a)
#define bitcount(x) __builtin_popcount(x)
#define cps CLOCKS_PER_SEC
#define PI acos(-1.0)
#define EPS 1e-9
#define mod 1000000007
#define MOD 1000000007
#define N 100005
#define M 50
using namespace std;

template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

template<typename T>
using maxpq = priority_queue<T>;

//All indexing is 0-based
using namespace __gnu_pbds;
typedef tree<pii, null_type, less<pii>, rb_tree_tag,
       tree_order_statistics_node_update> ordered_set;
//methods: find_by_order(k); & order_of_key(k);
//To make it an ordered_multiset, use pairs of (value, time_of_insertion)
//to distinguish values which are similar.

//a and b are assumed to be taken modulo p
inline int add(int a, int b, int p = mod){ ll c = a + b; if(c >= p) c -= p; return c;}
inline int sub(int a, int b, int p = mod){ int c = a - b; if(c < 0) c += p; return c;}
inline int mul(int a, int b, int p = mod){ return (a * 1ll * b) % p;}

int a[N];
int ft[N << 1];
int n;

void init() {
  memset(ft, 0, sizeof ft);
}

int query(int i) { //prefix sum upto a[i]
  i++;
  int ans = 0;
  while(i > 0) {
    ans += ft[i];
    i -= i & -i;
  }
  return ans;
}

int query(int i, int j) { //ranges sum from a[i] .. a[j]
  return query(j) - query(i - 1);
}

void increment(int i, int val) {
  i++;
  while(i <= (N << 1)) {
    ft[i] += val;
    i += i &-i;
  }
}

void update(int i, int val) {
  int old = query(i, i); //prev value at a[i]
  val = val - old; //total increment for the pos. a[i]
  increment(i, val);
}

class MajoritySubarray {
public:
  long long getCount(int n, int seed, int m) {
    ::n = n;
    rep(i, 0, n) {
      a[i] = (seed >> 16) % m;
      //has[a[i]] = 1;
      seed = (seed * 1103515245ll + 12345) & ((1ll << 31) - 1);
    }
    //int bal = n;
    ll ans = 0;
    rep(k, 0, m) {
      int bal = n;
      init();
      rep(i, 0, n) {
        increment(bal, 1);
        if(a[i] == k) bal++;
        else bal--;
        ans += query(bal-1);
        //db(bal), db(k), db(i), db(ans);
      }
    }
    return ans;
  }
};


main()
{ 
  #ifndef ONLINE_JUDGE
    freopen("/home/tarun/Desktop/input.txt", "r", stdin);
//    freopen("/home/tarun/Desktop/output.txt", "w", stdout);
  #endif
  sync;
  clock_t clk = clock();

  //cout << MajoritySubarray().getCount(100000, 2147483647, 2) << '\n';
  cout << MajoritySubarray().getCount(100000, 54534555, 50) << '\n';

  cerr << "Time (in ms): " << double(clock() - clk) * 1000.0 / cps << '\n';
}

//Compile using:
//g++ -o filename.exe --std=c++11 filename.cpp
//Use -D CP for defining a macro CP in the local environment