Vuong เป็นหนึ่งในนักคณิตศาสตร์ที่ยิ่งใหญ่ที่สุดตลอดกาล! งานอดิเรกของเขาคือการค้นหาคุณสมบัติทางคณิตศาสตร์ของทุกสิ่ง และบางครั้งรวมถึงสิ่งที่ไม่มีอยู่จริงด้วย! ในวันเกิดของเขา เพื่อนโปรแกรมเมอร์ได้มอบสตริงไบนารี $S$ ที่มีความยาว $n$ ให้กับเขา หลังจากนั้นไม่นาน เขาก็ค้นพบคุณสมบัติที่น่าสนใจมากสองประการของ $S$:

• $X(S)$: ความยาวของสตริงที่สั้นที่สุดที่ไม่ใช่ลำดับย่อยของ $S$

• $Y(S)$: จำนวนสตริงที่มีความยาว $X(S)$ ที่ไม่ใช่ลำดับย่อยของ $S$

เมื่อเห็นว่า Vuong สนุกกับการค้นหาคุณสมบัติทั้งสองนี้ เพื่อนโปรแกรมเมอร์ของเขาจึงคิดว่าคงจะดีไม่น้อยหากลองเปลี่ยนสตริง $S$ เล็กน้อย โปรแกรมเมอร์จะทำการแก้ไขสตริง $S$ ตามลำดับจำนวน $q$ ครั้ง การแก้ไขแต่ละครั้งจะเป็นหนึ่งในประเภทต่อไปนี้:

• 0 l r: กำหนดให้ $S_l,S_{l+1},\ldots,S_r$ เป็น $0$

• 1 l r: กำหนดให้ $S_l,S_{l+1},\ldots,S_r$ เป็น $1$

• F l r: พลิกค่า $S_l,S_{l+1},\ldots,S_r$ กล่าวคือ สำหรับ $l\le i\le r$ ถ้า $S_i$ เป็น $0$ ให้กำหนดเป็น $1$ มิฉะนั้นให้กำหนดเป็น $0$

และแน่นอนว่าสำหรับสตริง $S$ แต่ละเวอร์ชันที่ถูกแก้ไข Vuong ก็ยินดีที่จะหาค่า $X(S)$ และ $Y(S)$ เช่นกัน เพราะวันนี้เป็นวันเกิดของเขา!

แต่ปริศนาจะไม่สมบูรณ์หากไม่มีคำตอบ กำหนดสตริง $S$ และรายการการแก้ไข $q$ ครั้งบนสตริง $S$ จงช่วยเพื่อนโปรแกรมเมอร์หาค่า $X(S)$ และ $Y(S)$ สำหรับการแก้ไขแต่ละครั้ง เพื่อที่เขาจะได้ตรวจสอบผลลัพธ์ของ Vuong กับคำตอบ

เนื่องจากคำตอบอาจมีค่าใหญ่มาก โปรดแสดงผลคำตอบมอดูโล $10^9+7$

สตริง $a$ เป็นลำดับย่อยของสตริง $b$ ถ้าสามารถสร้าง $a$ จาก $b$ ได้โดยการลบอักขระออกบางตัว (อาจจะไม่ลบเลยหรือลบทั้งหมดก็ได้) ตัวอย่างเช่น bd, acd, b เป็นลำดับย่อยของ abcd ในขณะที่ da ไม่ใช่

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็มสองจำนวน $n,q$ ($1\le n,q\le100\,000$) แทนความยาวของสตริง $S$ และจำนวนการแก้ไข

บรรทัดที่สองประกอบด้วยสตริงไบนารี $S$ ที่มีความยาว $n$

บรรทัดที่ $i$ ใน $q$ บรรทัดถัดไปประกอบด้วยคำอธิบายของการดำเนินการครั้งที่ $i$ ในรูปแบบใดรูปแบบหนึ่งต่อไปนี้:

• 0 l r ($1\le l\le r\le n$): กำหนดให้ $S_l,S_{l+1},\ldots,S_r$ เป็น $0$

• 1 l r ($1\le l\le r\le n$): กำหนดให้ $S_l,S_{l+1},\ldots,S_r$ เป็น $1$

• F l r ($1\le l\le r\le n$): พลิกค่า $S_l,S_{l+1},\ldots,S_r$

ข้อมูลส่งออก

สำหรับการแก้ไขสตริง $S$ แต่ละครั้ง ให้แสดงผลจำนวนเต็มสองจำนวนคือ $X(S)$ และ $Y(S)$ มอดูโล $10^9+7$ ในหนึ่งบรรทัด

ตัวอย่าง

ข้อมูลนำเข้า 1

4 3
0110
0 2 3
1 3 4
F 2 3

ข้อมูลส่งออก 1

1 1
2 1
3 4

คำอธิบาย

ในตัวอย่าง สตริง $S$ คือ 0110 และมีการแก้ไขบน $S$ จำนวน $q=3$ ครั้ง

ตารางต่อไปนี้แสดงการแก้ไขของ $S$

• สำหรับ $S=$ 0000 จะได้ $X(S)=1$ และ $Y(S)=1$ เนื่องจากมีสตริงความยาว $1$ เพียงตัวเดียวที่ไม่ใช่ลำดับย่อยของ $S$ ซึ่งก็คือสตริง 1

• สำหรับ $S=$ 0011 สตริง 10 เป็นสตริงที่สั้นที่สุด และเป็นสตริงความยาว $2$ เพียงตัวเดียวที่ไม่ใช่ลำดับย่อยของ $S$

• สำหรับ $S=$ 0101 รายการของสตริงที่มีความยาวสั้นที่สุดที่ไม่ใช่ลำดับย่อยของ $S$ คือ {000, 100, 110, 111}

• สำหรับสตริงเริ่มต้น $S=$ 0110 รายการของสตริงที่มีความยาวสั้นที่สุดที่ไม่ใช่ลำดับย่อยของ $S$ คือ {000, 001, 100, 101, 111} ดังนั้น $X(S)=3$ และ $Y(S)=5$ แต่คุณไม่จำเป็นต้องแสดงผลตัวเลขสองตัวนี้