[Ynoi2014] 长存不灭的过去、逐渐消逝的未来

 【她遵守了约定哦...】 【从不可能存活的战场上】 【一心想着要见到技官...想要向技官撒娇...】 【才保留下了一点点寿命...平安回来了哦...】 没错...她遵守了约定... 可我却什么都没能和她说 什么都没能为她做 什么都...  ...... 珂朵莉......  以前我碰上他人的悲剧或是不幸这种无可奈何的事情时 总是设法想去改变什么 但是我的力量一直过于渺小...  到最后什么忙都没帮上... 我应该已经有深切体会了才对... 我想让珂朵莉幸福... 真受不了那个家伙... 像我这样的男人，到底有什么地方能让她看上啊...  【你连这点事情都想不明白吗？】 【因为你...是让我见识了许许多都第一次的人...】 【在露天摊贩街上，是你第一次救了我】 【是你第一次带我去视野开阔的地方眺望风景】 【是你让我第一次产生了各种各样的感情】 【你是第一个让我依赖的人，也是第一个将我击败的对手】  【啊...真要数起来根本数不完...】 【所以，我第一个喜欢上的人是你，是理所当然的事情】  【这点小事你好歹得察觉到啊，笨~蛋】 【我...究竟是怎么了？】 【我记得我回到仓库，做了奇怪的梦】  【你久久不回来...】 【你怎么了，露出这种表情？】 欢迎回来...珂朵莉  欢迎回来... 

珂朵莉定义项为指若干个（$\ge1$）数字（$0\cdots 9$）相连得到的字符串（如 `123` `000` 是合法的项，`** *-1 +5` 是不合法的项）。一个合法的表达式可以为一个项（如 `233`）、两个表达式以 `+ -*` 相连（如`2*3+5*5` `6-6*6`）、一个表达式在左右添一对括号（如 (`2*3*3`)）。 注意：空串不是一个合法的表达式。 在一开始，你会得到一个长为 $n$ 的字符串，之后会给定 $m$ 个操作。 有两种操作： `1 x y` 表示将位置 $x$ 的字符改成 $y$。 `2 l r` 表示询问 $[l,r]$ 的字符串作为表达式求值在$\bmod {10^9+7}$ 意义下的结果。若该串不是一个合法的表达式，结果为 $-1$。

第一行有两个整数 $n,m$。 第二行有一个长为 $n$ 的字符串。 接下来 $m$ 行，每行为 `1 x y` 或 `2 l r`，分别表示两种操作。

对所有 $2$ 的操作，输出一行，包含一个整数，表示答案。

5 12
2*(3)
2 1 1
2 4 4
2 1 5
1 3 2
2 1 5
2 1 4
2 1 3
2 2 3
1 1 (
1 2 5
1 3 +
2 1 5

2
3
6
-1
46
4
-1
8

Idea：mcfx，Solution：mcfx，Code：mcfx，Data：mcfx $1\leq n,m \leq 10^5$，$1 \leq l\leq r\leq n$，$1\leq x\leq n$。 字符集为 `0 1 2 3 4 5 6 7 8 9 + - * ( )` 若将 `(` 作为 $1$，`)` 作为 $-1$，其他字符作为 $0$，则保证在任意时刻，该串的任意前缀和的绝对值不超过 $50$。