#include #define show(x) cout << #x << " = " << x << endl using namespace std; using ll = long long; using pii = pair; using vi = vector; template ostream& operator<<(ostream& os, const vector& v) { os << "sz=" << v.size() << "\n["; for (const auto& p : v) { os << p << ","; } os << "]\n"; return os; } template ostream& operator<<(ostream& os, const pair& p) { os << "(" << p.first << "," << p.second << ")"; return os; } constexpr ll MOD = 1e9 + 7; template constexpr T INF = numeric_limits::max() / 100; struct Matrix { Matrix& operator=(const Matrix& m) { for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { table[i][j] = m.table[i][j]; } } return (*this); } Matrix operator*(const Matrix& m) const { Matrix result; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { ll v = 0; for (int k = 0; k < 4; k++) { v = (v + table[i][k] * m.table[k][j]) % MOD; } result.table[i][j] = v; } } return result; } static Matrix unit() { Matrix result; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { if (i == j) { result.table[i][i] = 1; } else { result.table[i][j] = 0; } } } return result; } static Matrix initial() { Matrix init; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { init.table[i][j] = 0; } } init.table[0][0] = 1; init.table[1][3] = 1; init.table[2][3] = 1; init.table[3][3] = 1; return init; } array, 4> table; }; ostream& operator<<(ostream& os, const Matrix& m) { os << "[" << endl; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { cout << m.table[i][j] << " "; } cout << endl; } cout << "]\n"; return os; } template struct SegmentTree { public: using BaseAlgebra = Base; using AccMonoid = typename BaseAlgebra::AccMonoid; using OpMonoid = typename BaseAlgebra::OpMonoid; using T = typename BaseAlgebra::T; using F = typename BaseAlgebra::OpMonoid::T; SegmentTree(const int n) : data_num(n), height(__lg(2 * data_num - 1)), size(1 << (1 + height)), half(size >> 1), value(size, AccMonoid::identity()), action(size, OpMonoid::identity()) { assert(n > 0); } SegmentTree(const std::vector& val) : data_num(val.size()), height(__lg(2 * data_num - 1)), size(1 << (1 + height)), half(size >> 1), value(size), action(size, OpMonoid::identity()) { for (int data = 0; data < half; data++) { if (data < data_num) { value[data + half] = val[data]; } else { value[data + half] = AccMonoid::identity(); } } for (int node = half - 1; node >= 1; node--) { value[node] = acc(value[2 * node], value[2 * node + 1]); } } T get(const int a) const { assert(0 <= a and a < data_num); return accumulate(a, a + 1); } void set(const int a, const T& val) { assert(0 <= a and a < data_num); const int node = a + half; value[node] = val; for (int i = node / 2; i > 0; i /= 2) { value[i] = acc(value[2 * i], value[2 * i + 1]); } } T accumulate(const int a, const int b) const // Accumulate (a,b] { assert(0 <= a and a < b and b <= data_num); return accumulateRec(1, 0, half, a, b); } void modify(const int a, const int b, const F& f) // Apply f on (a,b] { assert(0 <= a and a < b and b <= data_num); if (f == OpMonoid::identity()) { return; } modifyRec(1, 0, half, a, b, f); } private: void modifyRec(const int int_index, const int int_left, const int int_right, const int mod_left, const int mod_right, const F& f) { if (mod_left <= int_left and int_right <= mod_right) { value[int_index] = act(f, value[int_index]); action[int_index] = compose(f, action[int_index]); } else if (int_right <= mod_left or mod_right <= int_left) { // Do nothing } else { modifyRec(2 * int_index, int_left, (int_left + int_right) / 2, 0, half, action[int_index]); modifyRec(2 * int_index, int_left, (int_left + int_right) / 2, mod_left, mod_right, f); modifyRec(2 * int_index + 1, (int_left + int_right) / 2, int_right, 0, half, action[int_index]); modifyRec(2 * int_index + 1, (int_left + int_right) / 2, int_right, mod_left, mod_right, f); value[int_index] = acc(value[2 * int_index], value[2 * int_index + 1]); action[int_index] = OpMonoid::identity(); } } T accumulateRec(const int int_index, const int int_left, const int int_right, const int mod_left, const int mod_right) const { if (mod_left <= int_left and int_right <= mod_right) { return value[int_index]; } else if (int_right <= mod_left or mod_right <= int_left) { return AccMonoid::identity(); } else { return act(action[int_index], acc(accumulateRec(2 * int_index, int_left, (int_left + int_right) / 2, mod_left, mod_right), accumulateRec(2 * int_index + 1, (int_left + int_right) / 2, int_right, mod_left, mod_right))); } } const int data_num; // Num of valid data on leaves. const int height; const int size; const int half; vector value; // Tree for value(length: size) vector action; // Tree for action(length: half) bool has_lazy; const AccMonoid acc{}; const OpMonoid compose{}; const BaseAlgebra act{}; }; struct MatrixMonoid { using T = Matrix; struct AccMonoid { T operator()(const T& a, const T& b) const { return b * a; } static T identity() { return Matrix::unit(); } }; struct OpMonoid { using T = ll; T operator()(const T& /*f1*/, const T& /*f2*/) const { return 0; } static constexpr T identity() { return 0; } }; T operator()(const OpMonoid::T& /*f*/, const T& x) const { return x; } }; inline Matrix x_renewal(const Matrix& m, ll newval) { Matrix result; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { result.table[i][j] = m.table[i][j]; } } result.table[0][1] = newval; return result; } inline Matrix y_renewal(const Matrix& m, ll newval) { Matrix result; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { result.table[i][j] = m.table[i][j]; } } result.table[1][1] = (newval * newval) % MOD; result.table[1][2] = (2 * newval) % MOD; result.table[2][2] = newval; return result; } int main() { int n; cin >> n; vector initial_value(n, Matrix::initial()); SegmentTree seg(initial_value); int q; cin >> q; for (int i = 0; i < q; i++) { char c; cin >> c; if (c == 'x') { int ind; ll x; cin >> ind >> x; const auto m = seg.get(ind); const auto val = x_renewal(m, x); seg.set(ind, val); } else if (c == 'y') { int ind; ll y; cin >> ind >> y; const auto m = seg.get(ind); const auto val = y_renewal(m, y); seg.set(ind, val); } else { int ind; cin >> ind; if (ind == 0) { cout << 1 << endl; } else { const Matrix acc = seg.accumulate(0, ind); cout << (acc.table[0][0] + acc.table[0][1] + acc.table[0][2] + acc.table[0][3]) % MOD << endl; } } } return 0; }