Вам задана строка \(s\), состоящая из \(n\) символов 0 и/или 1.
Вы делаете \(m\) копий этой строки. Пусть \(i\)-я копия — это строка \(t_i\). Затем вы выполняете ровно одну операцию над каждой из копий: в \(i\)-й копии вы сортируете подстроку \([l_i; r_i]\) (подстроку, начинающуюся с \(l_i\)-го символа и заканчивающуюся \(r_i\)-м символом, обе границы включаются). Заметьте, что каждая операция затрагивает только одну копию, и каждая копия затрагивается только одной операцией.
Ваша задача — посчитать количество различных строк среди \(t_1, t_2, \ldots, t_m\). Заметьте, что изначальная строка \(s\) должна считаться только тогда, когда хотя бы одна копия остается неизменной после операции.
Выходные данные
Выведите одно целое число — количество различных строк среди \(t_1, t_2, \ldots, t_m\).
Примечание
Рассмотрим первый тестовый пример. Копии ниже представлены в порядке операций из входных данных. Сортируемые подстроки подчеркнуты:
- 101100 \(\rightarrow\) 011100;
- 101100 \(\rightarrow\) 011100;
- 101100 \(\rightarrow\) 101100;
- 101100 \(\rightarrow\) 101100;
- 101100 \(\rightarrow\) 000111.
Среди \(t_1, t_2, t_3, t_4, t_5\) всего три различные строки: 000111, 011100 и 101100.
Рассмотрим второй тестовый пример:
- 100111 \(\rightarrow\) 100111;
- 100111 \(\rightarrow\) 001111;
- 100111 \(\rightarrow\) 001111;
- 100111 \(\rightarrow\) 010111.
Среди \(t_1, t_2, t_3, t_4\) всего три различные строки: 001111, 010111 и 100111.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|