题目描述

面条老师听说你是个数据结构大师，所以来找你写数据结构了。快谢谢面条老师。

现在给你一段01串。

下面会有$q$次操作：

1. 选择一个区间$[L, R]$，将其中的01串升序或降序排列。
2. 选择一个区间$[L, R]$，询问01串从二进制转为十进制后模$1e9 + 7$的结果。

想必这道题你可以非常丝滑地完成。面条老师一脸期待地看着你。

输入格式

第一行一个仅由01构成的字符串，为面条老师初始所写的01串。

接下来一行一个整数$q$表示$q$次操作。形式为下列的一个：

• 1 L R : 将$[L, R]$中的01串降序排列。
• 2 L R : 将$[L, R]$中的01串升序排列。
• 3 L R : 将$[L, R]$中的01串从二进制转换至十进制并输出答案。

输出格式

对于每个3操作输出一行一个整数表示答案。

1010101
5
1 2 4
2 5 6
3 2 6
2 1 6
3 1 7

17
15

样例解释

数据规模与约定

定义01串的串长为$n$。

对于30%的数据，$1 \le n \le 1000$。

对于60%的数据，$1 \le n, q \le 5000$

对于100%的数据，$1 \le n, q \le 200000$

大样例

大样例下载