#include <bits/stdc++.h>
namespace ada {
class Xoroshiro128 {
public:
using result_type = uint32_t;
static constexpr result_type(min)() { return 0; }
static constexpr result_type(max)() { return UINT32_MAX; }
static inline result_type rotl(const result_type x, int k) {
return (x << k) | (x >> (32 - k));
}
Xoroshiro128() : Xoroshiro128(1, 2, 3, 4) {}
Xoroshiro128(result_type a, result_type b, result_type c, result_type d)
: s{a, b, c, d} {}
result_type operator()() {
const result_type result = rotl(s[0] + s[3], 7) + s[0];
const result_type t = s[1] << 9;
s[2] ^= s[0];
s[3] ^= s[1];
s[1] ^= s[2];
s[0] ^= s[3];
s[2] ^= t;
s[3] = rotl(s[3], 11);
return result;
}
private:
std::array<result_type, 4> s;
};
namespace {
int c_lead, c_team;
Xoroshiro128 rng;
} // namespace
int Init() {
int n;
uint32_t s1, s2, s3, s4;
std::cin >> n >> c_lead >> c_team >> s1 >> s2 >> s3 >> s4;
rng = Xoroshiro128(s1, s2, s3, s4);
return n;
}
int GetLeadership() { return uint64_t(rng()) * c_lead >> 32; }
int GetTeamValue() {
int tmp = int(uint64_t(rng()) * c_team >> 32) + 1;
return int(c_team / sqrt(tmp));
}
} // namespace ada
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7, INF = 1LL << 60;
const int maxn = 2e6 + 5;
int leadership[maxn], team_value[maxn];
ll prefix[maxn], seg[4 * maxn], lazy[4 * maxn];
inline void push(int index, int left, int right) {
if (lazy[index]) {
if (left != right) {
seg[2 * index] += lazy[index];
seg[2 * index + 1] += lazy[index];
lazy[2 * index] += lazy[index];
lazy[2 * index + 1] += lazy[index];
}
lazy[index] = 0;
}
}
void update(int index, int left, int right, int lo, int hi, ll val) {
push(index, left, right);
if (lo <= left && right <= hi) {
seg[index] += val;
lazy[index] += val;
push(index, left, right);
return;
}
int mid = (left + right) / 2;
if (hi <= mid)
update(2 * index, left, mid, lo, hi, val);
else if (lo > mid)
update(2 * index + 1, mid + 1, right, lo, hi, val);
else {
update(2 * index, left, mid, lo, hi, val);
update(2 * index + 1, mid + 1, right, lo, hi, val);
}
seg[index] = max(seg[2 * index], seg[2 * index + 1]);
}
int query(int index, int left, int right, int val) {
push(index, left, right);
if (left == right)
return left;
int mid = (left + right) / 2;
if (seg[2 * index + 1] <= val)
return query(2 * index, left, mid, val);
else
return query(2 * index + 1, mid + 1, right, val);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n = ada::Init();
for (int i = n; i > 0; --i)
leadership[i] = ada::GetLeadership();
for (int i = n; i > 0; --i)
team_value[i] = ada::GetTeamValue();
prefix[0] = 1;
update(1, 0, n, 0, 0, INF);
for (int i = 1; i <= n; ++i) {
int ind = query(1, 0, n, leadership[i]);
if (ind == 0)
prefix[i] = 2 * prefix[i - 1] % mod;
else
prefix[i] = (2 * prefix[i - 1] - prefix[ind - 1] + mod) % mod;
update(1, 0, n, 0, i, team_value[i]);
}
cout << (prefix[n] - prefix[n - 1] + mod) % mod << '\n';
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cm5hbWVzcGFjZSBhZGEgewpjbGFzcyBYb3Jvc2hpcm8xMjggewogcHVibGljOgogIHVzaW5nIHJlc3VsdF90eXBlID0gdWludDMyX3Q7CiAgc3RhdGljIGNvbnN0ZXhwciByZXN1bHRfdHlwZShtaW4pKCkgeyByZXR1cm4gMDsgfQogIHN0YXRpYyBjb25zdGV4cHIgcmVzdWx0X3R5cGUobWF4KSgpIHsgcmV0dXJuIFVJTlQzMl9NQVg7IH0KICBzdGF0aWMgaW5saW5lIHJlc3VsdF90eXBlIHJvdGwoY29uc3QgcmVzdWx0X3R5cGUgeCwgaW50IGspIHsKICAgIHJldHVybiAoeCA8PCBrKSB8ICh4ID4+ICgzMiAtIGspKTsKICB9CiAgWG9yb3NoaXJvMTI4KCkgOiBYb3Jvc2hpcm8xMjgoMSwgMiwgMywgNCkge30KICBYb3Jvc2hpcm8xMjgocmVzdWx0X3R5cGUgYSwgcmVzdWx0X3R5cGUgYiwgcmVzdWx0X3R5cGUgYywgcmVzdWx0X3R5cGUgZCkKICAgICAgOiBze2EsIGIsIGMsIGR9IHt9CiAgcmVzdWx0X3R5cGUgb3BlcmF0b3IoKSgpIHsKICAgIGNvbnN0IHJlc3VsdF90eXBlIHJlc3VsdCA9IHJvdGwoc1swXSArIHNbM10sIDcpICsgc1swXTsKICAgIGNvbnN0IHJlc3VsdF90eXBlIHQgPSBzWzFdIDw8IDk7CiAgICBzWzJdIF49IHNbMF07CiAgICBzWzNdIF49IHNbMV07CiAgICBzWzFdIF49IHNbMl07CiAgICBzWzBdIF49IHNbM107CiAgICBzWzJdIF49IHQ7CiAgICBzWzNdID0gcm90bChzWzNdLCAxMSk7CiAgICByZXR1cm4gcmVzdWx0OwogIH0KCiBwcml2YXRlOgogIHN0ZDo6YXJyYXk8cmVzdWx0X3R5cGUsIDQ+IHM7Cn07CgpuYW1lc3BhY2UgewoJaW50IGNfbGVhZCwgY190ZWFtOwoJWG9yb3NoaXJvMTI4IHJuZzsKCX0gIC8vIG5hbWVzcGFjZQoKCWludCBJbml0KCkgewoJICBpbnQgbjsKCSAgdWludDMyX3QgczEsIHMyLCBzMywgczQ7CgkgIHN0ZDo6Y2luID4+IG4gPj4gY19sZWFkID4+IGNfdGVhbSA+PiBzMSA+PiBzMiA+PiBzMyA+PiBzNDsKCSAgcm5nID0gWG9yb3NoaXJvMTI4KHMxLCBzMiwgczMsIHM0KTsKCSAgcmV0dXJuIG47Cgl9CgoJaW50IEdldExlYWRlcnNoaXAoKSB7IHJldHVybiB1aW50NjRfdChybmcoKSkgKiBjX2xlYWQgPj4gMzI7IH0KCglpbnQgR2V0VGVhbVZhbHVlKCkgewoJICBpbnQgdG1wID0gaW50KHVpbnQ2NF90KHJuZygpKSAqIGNfdGVhbSA+PiAzMikgKyAxOwoJICByZXR1cm4gaW50KGNfdGVhbSAvIHNxcnQodG1wKSk7Cgl9Cgp9ICAvLyBuYW1lc3BhY2UgYWRhCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwpjb25zdCBsbCBtb2QgPSAxZTkgKyA3LCBJTkYgPSAxTEwgPDwgNjA7CmNvbnN0IGludCBtYXhuID0gMmU2ICsgNTsKaW50IGxlYWRlcnNoaXBbbWF4bl0sIHRlYW1fdmFsdWVbbWF4bl07CmxsIHByZWZpeFttYXhuXSwgc2VnWzQgKiBtYXhuXSwgbGF6eVs0ICogbWF4bl07CmlubGluZSB2b2lkIHB1c2goaW50IGluZGV4LCBpbnQgbGVmdCwgaW50IHJpZ2h0KSB7CglpZiAobGF6eVtpbmRleF0pIHsKCQlpZiAobGVmdCAhPSByaWdodCkgewoJCQlzZWdbMiAqIGluZGV4XSArPSBsYXp5W2luZGV4XTsKCQkJc2VnWzIgKiBpbmRleCArIDFdICs9IGxhenlbaW5kZXhdOwoJCQlsYXp5WzIgKiBpbmRleF0gKz0gbGF6eVtpbmRleF07CgkJCWxhenlbMiAqIGluZGV4ICsgMV0gKz0gbGF6eVtpbmRleF07CgkJfQoJCWxhenlbaW5kZXhdID0gMDsKCX0KfQp2b2lkIHVwZGF0ZShpbnQgaW5kZXgsIGludCBsZWZ0LCBpbnQgcmlnaHQsIGludCBsbywgaW50IGhpLCBsbCB2YWwpIHsKCXB1c2goaW5kZXgsIGxlZnQsIHJpZ2h0KTsKCWlmIChsbyA8PSBsZWZ0ICYmIHJpZ2h0IDw9IGhpKSB7CgkJc2VnW2luZGV4XSArPSB2YWw7CgkJbGF6eVtpbmRleF0gKz0gdmFsOwoJCXB1c2goaW5kZXgsIGxlZnQsIHJpZ2h0KTsKCQlyZXR1cm47Cgl9CglpbnQgbWlkID0gKGxlZnQgKyByaWdodCkgLyAyOwoJaWYgKGhpIDw9IG1pZCkKCQl1cGRhdGUoMiAqIGluZGV4LCBsZWZ0LCBtaWQsIGxvLCBoaSwgdmFsKTsKCWVsc2UgaWYgKGxvID4gbWlkKQoJCXVwZGF0ZSgyICogaW5kZXggKyAxLCBtaWQgKyAxLCByaWdodCwgbG8sIGhpLCB2YWwpOwoJZWxzZSB7CgkJdXBkYXRlKDIgKiBpbmRleCwgbGVmdCwgbWlkLCBsbywgaGksIHZhbCk7CgkJdXBkYXRlKDIgKiBpbmRleCArIDEsIG1pZCArIDEsIHJpZ2h0LCBsbywgaGksIHZhbCk7Cgl9CglzZWdbaW5kZXhdID0gbWF4KHNlZ1syICogaW5kZXhdLCBzZWdbMiAqIGluZGV4ICsgMV0pOwp9CmludCBxdWVyeShpbnQgaW5kZXgsIGludCBsZWZ0LCBpbnQgcmlnaHQsIGludCB2YWwpIHsKCXB1c2goaW5kZXgsIGxlZnQsIHJpZ2h0KTsKCWlmIChsZWZ0ID09IHJpZ2h0KQoJCXJldHVybiBsZWZ0OwoJaW50IG1pZCA9IChsZWZ0ICsgcmlnaHQpIC8gMjsKCWlmIChzZWdbMiAqIGluZGV4ICsgMV0gPD0gdmFsKQoJCXJldHVybiBxdWVyeSgyICogaW5kZXgsIGxlZnQsIG1pZCwgdmFsKTsKCWVsc2UKCQlyZXR1cm4gcXVlcnkoMiAqIGluZGV4ICsgMSwgbWlkICsgMSwgcmlnaHQsIHZhbCk7Cn0KCmludCBtYWluKCkgewoJaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7CgljaW4udGllKDApOwoJaW50IG4gPSBhZGE6OkluaXQoKTsKCWZvciAoaW50IGkgPSBuOyBpID4gMDsgLS1pKQoJCWxlYWRlcnNoaXBbaV0gPSBhZGE6OkdldExlYWRlcnNoaXAoKTsKCWZvciAoaW50IGkgPSBuOyBpID4gMDsgLS1pKQoJCXRlYW1fdmFsdWVbaV0gPSBhZGE6OkdldFRlYW1WYWx1ZSgpOwoJcHJlZml4WzBdID0gMTsKCXVwZGF0ZSgxLCAwLCBuLCAwLCAwLCBJTkYpOwoJZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgKytpKSB7CgkJaW50IGluZCA9IHF1ZXJ5KDEsIDAsIG4sIGxlYWRlcnNoaXBbaV0pOwoJCWlmIChpbmQgPT0gMCkKCQkJcHJlZml4W2ldID0gMiAqIHByZWZpeFtpIC0gMV0gJSBtb2Q7CgkJZWxzZQoJCQlwcmVmaXhbaV0gPSAoMiAqIHByZWZpeFtpIC0gMV0gLSBwcmVmaXhbaW5kIC0gMV0gKyBtb2QpICUgbW9kOwoJCXVwZGF0ZSgxLCAwLCBuLCAwLCBpLCB0ZWFtX3ZhbHVlW2ldKTsKCX0KCWNvdXQgPDwgKHByZWZpeFtuXSAtIHByZWZpeFtuIC0gMV0gKyBtb2QpICUgbW9kIDw8ICdcbic7CglyZXR1cm4gMDsKfQ==