Truy vấn MOD

Trong một buổi biểu diễn guitar, FullHouse Dev được yêu cầu giải một bài toán thú vị về xử lý chuỗi nhị phân. Với niềm đam mê âm nhạc và lập trình, họ đã quyết định đương đầu với thử thách này trong lúc nghỉ giải lao giữa các tiết mục.

Bài toán

Cho một chuỗi nhị phân \(s\) và \(q\) truy vấn cần xử lý theo thứ tự. Chuỗi nhị phân là chuỗi chỉ chứa các ký tự 0 và 1.

Có hai loại truy vấn:

• Loại 1: Đảo bit tại vị trí \(i\) (0 thành 1 và 1 thành 0). Mỗi thay đổi sẽ ảnh hưởng đến các truy vấn tiếp theo.
• Loại 2: In ra giá trị thập phân của chuỗi con từ vị trí \(l\) đến \(r\) theo modulo \(10^9+7\).

Giá trị thập phân của một đoạn \([l,r]\) trong \(s\) là \(\sum_{i=l}^r s_i \times 2^{r-i}\), trong đó \(s_i\) là giá trị số nguyên của ký tự tại vị trí thứ \(i\) trong \(s\).

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) - độ dài chuỗi và số lượng truy vấn.
• Dòng thứ hai chứa chuỗi \(s\) chỉ gồm các ký tự 0 và 1.
• \(q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn:
  • Loại 1: "1 \(i\)" - đảo bit tại vị trí \(i\)
  • Loại 2: "2 \(l\) \(r\)" - tính giá trị thập phân của đoạn từ \(l\) đến \(r\) theo modulo \(10^9+7\)

OUTPUT FORMAT:

• Với mỗi truy vấn loại 2, in ra một số nguyên là giá trị thập phân của đoạn được truy vấn theo modulo \(10^9+7\).

Ràng buộc:

• \(1 \leq n \leq 10^5\)
• \(1 \leq q \leq 10^5\)

Ví dụ

INPUT

5 3
10101
2 1 5
1 2
2 1 3

OUTPUT

21
7

Giải thích

• Ở truy vấn đầu tiên, chuỗi con từ vị trí 1 đến 5 là "10101", có giá trị thập phân là 21.
• Ở truy vấn thứ hai, ta đảo bit tại vị trí 2, chuỗi trở thành "11101".
• Ở truy vấn cuối cùng, chuỗi con từ vị trí 1 đến 3 là "111", có giá trị thập phân là 7.