Cho một dãy ~A~ gồm ~N~ số nguyên ~A_1, A_2, A_3, \dots, A_N~ (các phần tử có giá trị từ ~1~ đến ~9~). Gọi ~S[L \dots R]~ là số nguyên được ghép bởi các số từ vị trí ~L~ đến vị trí ~R~ trong dãy ~A~, theo thứ tự từ trái sang phải. Ví dụ: với dãy ~A = [2, 6, 5, 7, 4]~ thì ~S[2 \dots 5]~ là số ~6574~.

Một số nguyên không âm được gọi là may mắn nếu như trong biểu diễn thập phân của số đó không chứa số ~13~. Ví dụ: các số may mắn là ~6, 12, 31, 103, \dots~; các số không may mắn là ~13, 5713, 321321, \dots~.

Yêu cầu: Bạn cần thực hiện ~Q~ yêu cầu thuộc một trong hai loại sau:

• Loại ~1~: Đưa ra số lượng các số may mắn không vượt quá ~S[L \dots R]~;

• Loại ~2~: Thay giá trị phần tử thứ ~i~ bằng giá trị ~X~.

Input

• Dòng đầu chứa hai số nguyên dương ~N, Q~ ~(N, Q \le 2 \cdot 10^5)~;

• Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, A_3, \dots, A_N~ viết liền nhau ~(1 \le A_i \le 9; 1 \le i \le N)~;

• ~Q~ dòng tiếp theo, mỗi dòng chứa một yêu cầu thuộc một trong hai dạng sau:

  • ~1\ L\ R~: Mô tả yêu cầu ghi ra số lượng số may mắn không vượt quá ~S[L \dots R]~ ~(1 \le L \le R \le N)~ sau khi chia dư cho ~10^9 + 7~;

  • ~2\ i\ X~: Mô tả yêu cầu thay giá trị phần tử thứ ~i~ bằng giá trị ~X~ ~(1 \le i \le N; 1 \le X \le 9)~.

Output

Với mỗi yêu cầu loại ~1~, ghi ra kết quả trên một dòng.

Scoring

Sample Input 1

6 3
849613
1 1 2
2 3 4
1 4 4

Sample Output 1

84
7

Notes

Với yêu cầu đầu tiên, các số may mắn không vượt quá ~84~ là ~0, 1, 2, \dots, 12, 14, 15, \dots, 84~.

Với yêu cầu thứ hai, dãy ~A~ là ~844613~.

Với yêu cầu thứ ba, các số may mắn không vượt quá ~6~ là ~0, 1, 2, \dots, 5, 6~.