매기의 숙제

매기 심슨이 서른 번째 시즌 만에 드디어 1학년이 되었다. 선생님은 글씨 연습을 위해 0부터 9까지의 숫자 N개를 원하는 순서로 한 줄에 적어 오라는 숙제를 냈다.

몇 시간을 씨름한 끝에 매기는 숙제를 마치고 친구들과 놀러 나갔다. 숙제는 책상 위에 그대로 남았다. 그때 리사 심슨이 방에 들어와 그 공책을 보게 되었다.

리사는 적힌 숫자들의 합을 금방 구했다. 그러자 바트 심슨이 더 어려운 문제를 냈다. 이 숫자 문자열에 M번의 연산을 수행하라는 것이다. 위치는 왼쪽부터 1번에서 N번까지 번호가 매겨지고, 연산은 두 종류다.

1 $l_i$ $r_i$ $c_i$: $l_i$번 위치부터 $r_i$번 위치까지의 모든 숫자를 숫자 $c_i$로 바꾼다.

2 $l_i$ $r_i$: $l_i$번 위치부터 $r_i$번 위치까지의 구간에서 부분 문자열로 나타나는 모든 수를 더한다. 같은 수가 구간에 여러 번 나오면 나온 횟수만큼 더한다. 0으로 시작하는 부분 문자열은 올바른 십진수 표기가 아니므로 합에 넣지 않는다. 답은 $10^9 + 7$로 나눈 나머지를 출력한다.

첫째 줄에 숫자의 개수 N과 바트의 연산 개수 M이 공백으로 구분되어 주어진다($1 \le N, M \le 100000$).

둘째 줄에는 0부터 9까지의 숫자 N개가 공백으로 구분되어 주어진다.

이후 M개의 줄에 연산이 주어진다. 1 $l_i$ $r_i$ $c_i$ 형태는 첫 번째 종류의 연산이며 $1 \le l_i \le r_i \le N$, $0 \le c_i \le 9$이다. 2 $l_i$ $r_i$ 형태는 두 번째 종류의 연산이며 $1 \le l_i \le r_i \le N$이다.

두 번째 종류의 연산마다 답을 $10^9 + 7$로 나눈 나머지를 한 줄에 하나씩 출력한다. 두 번째 종류의 연산이 없으면 아무것도 출력하지 않는다.

첫 번째 예제에서 첫 번째 2번 연산의 답은 $1 + 12 + 121 + 2 + 21 + 1 = 158$이다. 두 번째 2번 연산의 답은 $2 + 20 + 203 + 0 + 3 = 228$이다. 03은 올바른 정수의 십진수 표기가 아니므로 이 구간에서는 더해지는 항이 더 적다.