Bánh mì

Một chiếc bánh mì được chia thành $n$ phần, đánh số từ $1$ đến $n$. Phần thứ $i$ có độ ngon $x_i\in \{0,1\}$.

Khi ăn các phần bánh, người ăn lần lượt chọn một phần bất kỳ trong số các phần còn lại và ăn nó. Nếu phần được chọn là phần thứ $i$ (với độ ngon hiện tại là $x_i$) thì:

• Độ thoả mãn của người ăn tăng thêm $x_i$;
• Độ ngon của tất cả các phần còn chưa ăn cũng tăng thêm $x_i$.

Độ thoả mãn ban đầu bằng $0$.

Ví dụ, nếu ba phần có độ ngon $[0,1,0]$: ăn phần thứ hai trước thì độ thoả mãn thành $1$ và các phần còn lại trở thành $[1,\_,1]$; tiếp tục ăn phần thứ nhất thì độ thoả mãn thành $2$ và còn lại $[\_,\_,2]$; ăn nốt phần cuối cho độ thoả mãn $4$.

Cho $q$ truy vấn, mỗi truy vấn gồm hai số $l$ và $r$. Với mỗi truy vấn, hãy tính độ thoả mãn lớn nhất có thể đạt được nếu chỉ ăn đúng các phần có chỉ số trong đoạn $[l,r]$, theo một thứ tự tuỳ ý.

Các truy vấn độc lập với nhau: mỗi truy vấn đều bắt đầu từ chiếc bánh ban đầu. Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• Dòng thứ hai chứa xâu gồm $n$ ký tự '0' hoặc '1'; ký tự thứ $i$ là độ ngon $x_i$ của phần thứ $i$.
• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l_i$ và $r_i$ mô tả một truy vấn.

Dữ liệu ra

In ra $q$ dòng, dòng thứ $i$ là đáp án của truy vấn thứ $i$, lấy phần dư cho ${10}^9+7$.

Ràng buộc

• $1\le n,q\le 100000$
• $x_i\in \{0,1\}$
• $1\le l_i\le r_i\le n$

Ví dụ