题目背景

【她遵守了约定哦...】
【从不可能存活的战场上】
【一心想着要见到技官...想要向技官撒娇...】
【才保留下了一点点寿命...平安回来了哦...】
没错...她遵守了约定...
可我却什么都没能和她说
什么都没能为她做
什么都...

......
珂朵莉......

以前我碰上他人的悲剧或是不幸这种无可奈何的事情时
总是设法想去改变什么
但是我的力量一直过于渺小...

到最后什么忙都没帮上...
我应该已经有深切体会了才对...
我想让珂朵莉幸福...
真受不了那个家伙...
像我这样的男人，到底有什么地方能让她看上啊...

【你连这点事情都想不明白吗？】
【因为你...是让我见识了许许多都第一次的人...】
【在露天摊贩街上，是你第一次救了我】
【是你第一次带我去视野开阔的地方眺望风景】
【是你让我第一次产生了各种各样的感情】
【你是第一个让我依赖的人，也是第一个将我击败的对手】

【啊...真要数起来根本数不完...】
【所以，我第一个喜欢上的人是你，是理所当然的事情】

【这点小事你好歹得察觉到啊，笨~蛋】
【我...究竟是怎么了？】
【我记得我回到仓库，做了奇怪的梦】

【你久久不回来...】
【你怎么了，露出这种表情？】
欢迎回来...珂朵莉

欢迎回来...

题目描述

珂朵莉定义项为指若干个（$\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$。