고장난 계산기 (Calculator) 게임

당신은 길을 가다가 수상한 계산기를 주웠다. 그 순간 뒤에서 살인마가 나타났고, 당신은 힘껏 달렸지만 결국 막다른 길에 다다르고 말았다. 뒤에서 '게임을 시작하지'라는 목소리가 들리자 계산기에 수식이 나타났다. 목숨을 건 게임이 시작되었다.

게임은 계산기의 수식을 계산하는 것이다. 다만 고장난 계산기와 함께하는 이 게임의 규칙을 따르기는 쉽지 않다.

1. 수식의 길이는 N이며, 0부터 9까지의 숫자와 '+', '*' 연산기호로 이루어져 있다.
2. 수식의 값을 계산할 때, 수식의 맨 앞에 오거나 바로 앞에 연산기호가 오는 연산기호는 모두 무시한다. 그다음 수식의 맨 끝 문자가 연산기호라면, 그 연산기호도 무시한다.
3. 수식의 값을 계산할 때 '*' 연산을 '+' 연산보다 먼저 계산한다.
4. 수식의 값은 항상 $10^9+7$로 나눈 나머지로 계산한다.
5. 연산기호만 있는 수식의 값은 -1이다.

예를 들어 '**11+*3*+5++'는 '11+3*5'로 보고 26이라고 답해야 하고, '**+++**+++'는 -1이라고 답해야 한다.

원래는 이렇게 수식의 값을 계산하고 게임을 끝낼 생각이었다. 그런데 수상할 정도로 레이팅이 높은 참가자들이 쿼리 문제를 넣어 달라고 계속 압박했다. 그래서 계산기에 적힌 수식은 Q번에 걸쳐 바뀌게 되었다.

쿼리는 l r x 형태로 주어진다. 수식의 l번째 문자부터 r번째 문자까지의 숫자에 x를 더한다는 뜻이다. 단, 쿼리를 처리할 때에만 '+', '*'도 숫자로 취급하며, 두 문자의 값은 각각 10과 11이다. 더한 결과가 12 이상이면 12로 나눈 나머지를 적용한다.

계산기 화면에 나타나는 총 Q+1개의 수식의 값을 모두 계산해서 목숨을 건 게임에서 살아남자!

첫째 줄에 N, Q가 주어진다. $1 \le N \le 100{,}000$, $1 \le Q \le 100{,}000$이다.

둘째 줄에는 길이 N의 수식이 주어진다.

셋째 줄부터 Q개의 줄에 쿼리가 한 줄에 하나씩 주어진다. $1 \le l \le r \le N$, $1 \le x < 12$이다.

첫째 줄에 입력으로 주어진 수식의 값을 $10^9+7$로 나눈 나머지를 출력한다. 수식이 연산기호로만 이루어진 경우 -1을 출력한다.

둘째 줄부터 Q+1번째 줄까지, i번째 줄에는 i-1번째 쿼리를 적용한 이후 수식의 값을 $10^9+7$로 나눈 나머지를 출력한다. 수식이 연산기호로만 이루어진 경우 -1을 출력한다.