계산 실수

수찬이는 덧셈과 뺄셈만 하는 계산기를 쓴다. 계산기에는 숫자 버튼 0부터 9까지, 연산 기호 버튼 +와 -, 결과를 보여주는 = 버튼, 계산기 상태를 처음으로 되돌리는 AC 버튼이 있다. 입력하고 있는 수만 지우는 C 버튼은 없다.

수식을 순서대로 입력하고 = 버튼을 누르면 화면에 계산 결과가 나온다. 다룰 수 있는 수의 범위에는 제한이 없고, 0으로 시작하는 수를 입력해도 된다. 연산 기호를 잘못 눌러 계산이 틀어지는 일을 막으려고 계산기는 세 가지 규칙을 따른다.

1. 연산 기호가 연속해서 나오면 가장 나중에 나온 것만 취한다.
2. 수식이 연산 기호로 시작하면 그 앞에 0을 붙였다고 본다.
3. 수식이 연산 기호로 끝나면 그 기호를 무시한다.

예를 들어 -15+0035-+-3-을 차례로 누른 뒤 =를 누르면 계산기는 $0 - 15 + 35 - 3$을 계산해 17을 보여준다. - 하나만 누르고 =를 누르면 수식이 $0-$이 되었다가 마지막 -가 무시되어 결과는 0이다.

C 버튼이 없으니 숫자 하나를 잘못 눌러도 AC를 누르고 수식을 처음부터 다시 입력해야 한다. 수찬이는 이 불편을 없애려고 다음 자료구조를 만들기로 했다.

0부터 9, +, -로만 이루어진 길이 $N$인 문자열 $S$가 있다. 문자열 $X$와 $1 \le i \le j \le |X|$에 대해, $X[i..j]$는 $X$의 $i$번째 문자부터 $j$번째 문자까지를 이어 붙인 부분문자열이다.

아래 두 연산을 지원하는 자료구조를 구현하라.

1. 바꾸기: $S[a..b]$를 길이가 $b - a + 1$인 새 문자열 $T$로 바꾼다. 즉 $a \le i \le b$인 모든 $i$에 대해 $S[i]$를 $T[i - a + 1]$로 바꾼다.
2. 계산하기: AC 버튼을 누른 뒤 $S[a..b]$를 계산기에 입력하고 = 버튼을 눌렀을 때 화면에 나오는 값을 구한다.

첫째 줄에 문자열의 길이 $N$ ($1 \le N \le 200\,000$)이 주어진다.

둘째 줄에 문자열 $S$가 주어진다. $S$의 길이는 $N$이다.

셋째 줄에 질의의 수 $Q$ ($1 \le Q \le 300\,000$)가 주어진다.

다음 $Q$개의 줄에 연산이 한 줄에 하나씩 주어진다. 각 줄의 형식은 아래와 같다.

• 바꾸기 연산은 1 a b T 형식이다. $a$와 $b$는 $1 \le a \le b \le N$을 만족하는 정수이고, $T$는 길이가 $b - a + 1$인 문자열이다. 모든 바꾸기 연산에서 주어지는 $T$의 길이의 합은 $200\,000$ 이하이다.
• 계산하기 연산은 2 a b 형식이다. $a$와 $b$는 $1 \le a \le b \le N$을 만족하는 정수이다. 계산하기 연산은 적어도 하나 주어진다.

입력으로 주어지는 문자열은 모두 0부터 9, +, -로만 이루어져 있다.

계산하기 연산이 주어질 때마다 계산 결과를 $10^9 + 7$로 나눈 나머지를 한 줄에 하나씩 출력한다. 정수 $x$를 $10^9 + 7$로 나눈 나머지는, 정수 $q$와 $r$가 $x = q(10^9 + 7) + r$와 $0 \le r < 10^9 + 7$을 만족할 때의 $r$의 값이다.