#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int llint; #define mp make_pair #define mt make_tuple #define pub push_back #define puf push_front #define pob pop_back #define pof pop_front #define fir first #define sec second #define res resize #define ins insert #define era erase const llint mod=1000000007; const llint big=1e17-10; const long double pai=3.141592653589793238462643383279; template void mineq(T& a,U b){if(a>b){a=b;}} template void maxeq(T& a,U b){if(a #include #include #include //永夜作 template std::enable_if_t< std::is_unsigned::value, Arithmetic> ipow(Arithmetic bace, Integral n) { //繰り返し二条法 auto res = (Arithmetic)(1); while (n > 0) { if (n & 1) res *= bace; bace *= bace; n >>= 1; } return res; } template class mint_base; //mint_base_base型用の累乗関数 template constexpr mint_base m_pow(mint_base x, uint64_t n)noexcept; //mod計算を自動で行う整数テンプレートクラス template class mint_base { public: //operator llint() const{return a;} static constexpr auto MOD = MOD_; static_assert(!(MOD <= 2), "MOD cannot be below 2."); static_assert(MOD <= (0xFFFFFFFFFFFFFFFF / 2), "MOD is too big");//加算してオーバーフローしない static_assert(MOD <= 0xFFFFFFFF, "MOD is too big");//乗算してオーバーフローしない constexpr mint_base operator+(const mint_base &other)const noexcept { auto v = *this; return v += other; } constexpr mint_base operator-(const mint_base &other)const noexcept { auto v = *this; return v -= other; } constexpr mint_base operator*(const mint_base &other)const noexcept { auto v = *this; return v *= other; } constexpr auto operator/(const mint_base &other)const noexcept { auto v = *this; return v /= other; } constexpr mint_base& operator+=(const mint_base &other) noexcept { a += other.a; if (MOD <= a) { a -= MOD; }; return *this; } constexpr mint_base& operator-=(const mint_base &other) noexcept { if (a >= other.a) { a -= other.a; } else { a = (a + MOD) - other.a; } return *this; } constexpr mint_base& operator*=(const mint_base &other) noexcept { #if 1 a *= other.a; a %= MOD; #else //MOD <= (MAXUINT64 / 2)条件下 uint64_t b = other.a, v = 0; while (b > 0) { if (b & 1) { v += a; if (v >= MOD)v -= MOD; } a += a; if (MOD <= a)a -= MOD; b >>= 1; } a = v; #endif return *this; } constexpr mint_base& operator/=(const mint_base &other) noexcept { return *this *= ~other; } constexpr mint_base operator+()const noexcept { return *this; } constexpr mint_base operator-()const noexcept { return{ MOD - a, mod_value_tag{} }; } constexpr mint_base& operator++() noexcept { if (MOD <= ++a) { a = 0; }; return *this; } constexpr mint_base& operator--() noexcept { if (a <= 0) { a = MOD; }; --a; return *this; } constexpr mint_base operator++(int) noexcept { auto tmp = *this; ++*this; return tmp; } constexpr mint_base operator--(int) noexcept { auto tmp = *this; --*this; return tmp; } constexpr mint_base operator~()const noexcept { return ipow(*this, e_phi - 1); } constexpr mint_base& operator=(const mint_base &other) noexcept { a = other.a; return *this; } constexpr explicit operator uint64_t()const noexcept { return a; } constexpr explicit operator unsigned()const noexcept { return (unsigned)a; } static constexpr uint64_t getmod() noexcept { return MOD; } constexpr mint_base(uint64_t a_) noexcept :a(a_ % MOD) {} constexpr mint_base()noexcept : a(0) {} struct mod_value_tag {}; constexpr mint_base(uint64_t a_, mod_value_tag) :a(a_) {} private: static constexpr uint64_t get_e_phi()noexcept { //オイラー値の導出 uint64_t temp = MOD; uint64_t m_ = MOD; for (uint64_t i = 2; i * i <= m_; ++i) { if (m_ % i == 0) { temp = temp / i * (i - 1); for (; m_ % i == 0; m_ /= i); } } if (m_ != 1)temp = temp / m_ * (m_ - 1); return temp; } static constexpr uint64_t e_phi = get_e_phi();//オイラー値 uint64_t a; }; //mint_base型のstreamへの出力 template std::ostream& operator<<(std::ostream& os, mint_base i) { os << (uint64_t)i; return os; } //mint_base型のstreamからの入力 template std::istream& operator >> (std::istream& is, mint_base& i) { uint64_t tmp; is >> tmp; i = tmp; return is; } typedef mint_base<1000000007> mint; namespace mint_literal { constexpr mint operator""_mi(unsigned long long x)noexcept { return mint(x); } } class segobj{ public:mint_base p,q,r,s,t; segobj(void){p=0;q=0;r=0;s=0;t=1;} segobj(mint_base a,mint_base b,mint_base c,mint_base d,mint_base e){p=a;q=b;r=c;s=d;t=e;} };//セグ木に乗せるもの segobj objtani=segobj(0,0,0,0,1);//単位元or初期値 実はconstです(頭がない) segobj ope(segobj lef,segobj rig){ return segobj( lef.p + rig.p*lef.s*lef.s, lef.q + rig.q*lef.s + lef.s*lef.t*rig.p*(mint_base)2, lef.r + rig.r + lef.t*rig.q + lef.t*lef.t*rig.p, lef.s*rig.s, lef.t*rig.s + rig.t ); }//オブジェクトの演算 class seg_tree_mono{ public: //区間加算できない代わりに、早く?、任意のモノイド演算が可能です //セグ木に変なものを乗せれる!! //区間を作るのを遅延します。区間が10^12あってっもおk segobj val; llint seghi,segmg; seg_tree_mono *left; seg_tree_mono *right; seg_tree_mono(llint hi,llint mg){ seghi=hi;segmg=mg;val=objtani; left=nullptr;right=nullptr; } ~seg_tree_mono(){delete left;delete right;} void make_ko(void){ if(this->left==nullptr&&segmg-seghi>1){ this->left=new seg_tree_mono(seghi,(seghi+segmg)/2); this->right=new seg_tree_mono((seghi+segmg)/2,segmg); } } void seg_chan(llint pot,segobj kou){ //更新クエリ if(this->seghi+1==this->segmg){this->val=kou;return;} make_ko(); if(potsegmg){left->seg_chan(pot,kou);} else{right->seg_chan(pot,kou);} this->val=ope(left->val,right->val); return; } segobj ask_mono(llint hi,llint mg){ //区間演算クエリー if(hi<=seghi&&segmg<=mg){return this->val;} if(mg<=seghi||segmg<=hi){return segobj(0,0,0,1,0);} make_ko(); segobj leret,riret; leret=left->ask_mono(hi,mg); riret=right->ask_mono(hi,mg); return ope(leret,riret); } }; int main(void){ llint n,m;cin>>n>>m; seg_tree_mono siki(0,n+1); for(int i=0;i>que; if(que=='x'){ llint j,v;cin>>j>>v; auto it=siki.ask_mono(j,j+1); it.p=v; siki.seg_chan(j,it); }else if(que=='y'){ llint j,v;cin>>j>>v; auto it=siki.ask_mono(j,j+1); it.s=v; siki.seg_chan(j,it); }else if(que=='a'){ int j;cin>>j; auto it=siki.ask_mono(0,j); cout<<(it.p+it.q+it.r+(mint_base)1)<