1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

#include <bits/stdc++.h>
#define For(i, l, r) for (long long i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (long long i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 1000100;

template<typename type>
type read() {
  type s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}

long long n, ans;
long long len, prelen, t0, pre, a, b, c, d, ppre;
long long vis[233], num[maxn], dp[maxn], opt[maxn];
bool isCeq0;
int32_t main() {
  n = read<long long>();
  t0 = read<long long>();
  a = read<long long>();
  b = read<long long>();
  c = read<long long>();
  d = read<long long>();
  if (c == 0) {
    isCeq0 = 1;
  }
  if (t0 == 0 && c == 0) {
    cout << n << endl;
    return 0;
  }
  if (n > 1000000) {
    pre = t0;
    num[1] = t0;
    long long flg = 0;
    dp[1] = 1;
    For(i, 2, 10000) {
      dp[i] = 1;
      ppre = pre;
      pre = (a * pre * pre + b * pre + c) % d;
      if (vis[pre] && flg == 1) break;
      if (vis[pre]) {
	flg = 1;
      }
      vis[pre] = i;
      num[i] = pre;
      
    }
    long long ende = vis[ppre] - 1, lstn = ppre;
    For(i, 1, ende) {
      if (num[i] == lstn) {
	prelen = i - 1;
	len = ende - i + 1;
	break;
      }
    }
    long long tms = (n - 1ll * prelen) /  len;
    ende += len * 149;
    int len_max = 0;
    pre = t0;
    num[1] = t0;
    For(i, 2, ende) {
      num[i] = pre = (a * pre * pre + b * pre + c) % d;
    }
    int pos0 = 0;
    For(i, 1, ende) {
      if (!pos0 && num[i] == 0) pos0 = i;
      if (num[i] >= opt[len_max]) {
	opt[++len_max] = num[i];
	dp[i] = len_max;
      } else {
	int pos = lower_bound(opt + 1, opt + 1 + len_max, num[i]) - opt;
	opt[pos] = num[i];
	dp[i] = pos;
      }
    }
    int tmp = 0;
    for (long long i = prelen + 1; i <= n - len * tms; i++) {
     if (num[i] == opt[len_max]) tmp++;
   }
    if (isCeq0)
      cout << max(len_max * 1ll, n - pos0 + 1) << endl;
    else
      cout << len_max + tms - 150 + tmp<< endl;
    
  } else {
    int len_max = 0;
    pre = t0;
    num[1] = t0;
    For(i, 2, n) {
      num[i] = pre = (a * pre * pre + b * pre + c) % d;
    }
    int pos0 = 0;
    For(i, 1, n) {
      if (!pos0 && num[i] == 0) pos0 = i;
      if (num[i] >= opt[len_max]) {
	opt[++len_max] = num[i];
	dp[i] = len_max;
      } else {
	int pos = lower_bound(opt + 1, opt + 1 + len_max, num[i]) - opt;
	opt[pos] = num[i];
	dp[i] = pos;
      }
    }
    if (isCeq0)
      cout << max(len_max * 1ll, n - pos0 + 1) << endl;
    else
      cout << len_max << endl;
  }
  return 0;
}

/*
  10
  1 1 3 5 37
  1 9 2 15 16 13 28 22 0 5 8 19 16
*/