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
#include <bits/stdc++.h>
using ll = long long;
using sz = size_t;
using namespace std;

// make the code less c++-readable:
template<class T> using v = vector<T>; 
template<class T> using vv = v<v<T>>; 
using vi = v<int>; using vll = v<ll>; using vvi = vv<int>; using vvll = vv<ll>;

// hai loading utilities
#define $T template<class T>
#define $Ts template<class... T>
$T T Load() { T v; cin >> v; return v; }
$T auto Loads(int n) { v<T> v; v.reserve(n); while(n--) v.emplace_back(Load<T>()); return v; }
$T auto Loads() { return Loads<T>(Load<int>()); }
template<class T, int N> auto Loada() { array<T, N> a; for (T& v: a) v = Load<T>(); return a; }
$Ts auto Cols(int rows) { tuple<v<T>...> t; while(rows--) [&]<sz... I>(index_sequence<I...>){(std::get<I>(t).push_back(Load<T>()), ...);}(index_sequence_for<T...>{}); return t; }
//$Ts auto Rows(int rows) { v<tuple<T...>> v; while(rows--) { v.emplace_back(Load<T>()...); } return v; } bugged :(
struct _aIV { $T operator vector<T>() { return Loads<T>(n); } sz n; };
struct _aI { $T operator T() { return Load<T>(); } _aIV operator()(sz n) { return {n}; } }; static inline _aI $;  /* int N = $;  vi Y = $(N); */
#define MAKE_LOADER(T, alias) \
  T alias() { return Load<T>(); }   /* int x = Int(); */\
  auto alias##s() { return Loads<T>(); }   /* vector<> xs = Ints(); */\
  auto alias##s(int n) { return Loads<T>(n); }   /* vector<> xs = Ints(7); */\
  template<int N> auto alias##a() { return Loada<T, N>(); }   /* array<> xs = Inta<7>();  */\
// line intentionally left blank
MAKE_LOADER(int, Int)
MAKE_LOADER(long long, LL)
MAKE_LOADER(char, Char)
MAKE_LOADER(string, String)
// kthxbye

constexpr ll M = 1'000'000'000+7;
constexpr int SZ = 1<<19;

struct MD {
    ll mno = 0, dod = 0;
};

void test() {
    int N = $;
    int Q = $;

    vll MNO(N);
    vll DOD(N);

    vll prefsum(N+1); // suma DOD; bez elementu
    vi najblimnoż(N+1); // piersze nietrywialne mnożenie
    najblimnoż[N] = N;

    for (int i = 0; i < N; ++i) {
        DOD[i] = $;
        prefsum[i+1] = prefsum[i] + DOD[i];
        MNO[i] = $;
    }

    for (int i = N-1; i >= 0; --i) {
        if (MNO[i] > 1) {
            najblimnoż[i] = i;
        } else {
            najblimnoż[i] = najblimnoż[i+1];
        }
    }


    v<MD> Drzewo(2*SZ);
    for (int i = 0; i < N; ++i) {
        if (MNO[i] > 1)
            Drzewo[SZ+i] = MD{.mno = MNO[i], .dod = 0};
        else            
            Drzewo[SZ+i] = MD{.mno = 1, .dod = DOD[i]};
    }
    for (int i = SZ-1; i > 0; --i) {
        Drzewo[i] = MD{
            .mno = (Drzewo[i*2].mno * Drzewo[i*2+1].mno) % M,
            .dod = (Drzewo[i*2].dod * Drzewo[i*2+1].mno + Drzewo[i*2+1].dod) % M,
        };
    }

	for (int i = 0; i < Q; ++i) {
        ll v = $;
        bool dużo = false;
        int l = $;
        int r = $;

        int p = l;

        // Najpierw czekamy na dużo.
        while (p < r && !dużo) {
            if (MNO[p] > 1) {
                v = max(v * MNO[p], v + DOD[p]);
                if (v >= M) dużo = true;
                v %= M;
                ++p;
            } else {
                assert(najblimnoż[p] > p);
                int pkoń = min(najblimnoż[p]-1, r-1); // włącznie od p do pkoń przejdziemy
                ll psuma = prefsum[pkoń+1] - prefsum[p];
                v += psuma;
                if (v >= M) dużo = true;
                v %= M;
                p = pkoń + 1;
            }
        }

        // Jest dużo (lub koniec)

        while (p < r) {
            int poziom = min<int>(countr_zero(unsigned(p)), bit_width(unsigned(r+1-p))-2);
            int i = ((SZ+p) >> poziom);
            v = (v*Drzewo[i].mno + Drzewo[i].dod) % M;
            p += 1<<poziom;
        }
        cout << v << endl;
    }
}


[[maybe_unused]] void jeden_test() { test(); }
[[maybe_unused]] void wiele_test() { int T = $; while (T--) test(); }

int main() {
    jeden_test();
    return 0;
}