数字符串
Background
Special for beginners, ^_^
Description
输入 T(≤1e6) 表示 T 组数据。所有数据的 n 之和 ≤2e6，m 之和 ≤2e6。
每组数据输入 n(1≤n≤2e6) m(1≤m≤2e6) 和长为 n 的 01 字符串 s。
然后输入 m 个操作，每个操作输入两个下标 i 和 j (1≤i≤j≤n)。
每次操作，复制一份 s，记作 t，然后把 t[i] 到 t[j] 排序，即区间 [i,j] 内的 0 排在 1 的前面。 这 m 次操作可以得到多少个不同的字符串？
Format
Input
输入 T(≤1e6) 表示 T 组数据。所有数据的 n 之和 ≤2e6，m 之和 ≤2e6。
每组数据输入 n(1≤n≤2e6) m(1≤m≤2e6) 和长为 n 的 01 字符串 s。
然后输入 m 个操作，每个操作输入两个下标 i 和 j (1≤i≤j≤n)。
Output
每行输出一组数据对应的答案。
Samples
3
6 5
101100
1 2
1 3
2 4
5 5
1 6
6 4
100111
2 2
1 4
1 3
1 2
1 1
0
1 1
3
3
1
Limitation
1s, 1024KiB for each test case.