Один из друзей Аркадия работает на огромном радиотелескопе. Несколько десятилетий назад телескоп послал сигнал \(s\) в соседнюю галактику. Кто бы мог подумать, но недавно от инопланетян пришёл ответ — сигнал \(t\)! Учёные хотят проверить, есть ли сходство между сигналами \(s\) и \(t\) или нет.
Исходный сигнал \(s\) был последовательностью нулей и единиц (все знают, что битовая запись является межгалактическим стандартом). Но полученный сигнал \(t\), однако, выглядит более замысловато, чем \(s\). Однако учёные не сдались и представили \(t\) как последовательность латинских букв. Учёные считают, что \(s\) и \(t\) похожи, если можно заменить все нули в \(s\) на некоторую строку \(r_0\), а все единицы в \(s\) на некоторую иную строку \(r_1\) так, что получится строка \(t\). Строки \(r_0\) и \(r_1\) должны быть различными и не пустыми.
Помогите другу Аркадия и посчитайте количество возможных замен нулей и единиц (то есть количество пар строк \(r_0\) и \(r_1\)), которые превращают \(s\) в \(t\).
Выходные данные
Выведите одно целое число — количество пар строк \(r_0\) и \(r_1\), которые переводят \(s\) в \(t\).
В случае, если ни одной подходящей пары нет, выведите \(0\).
Примечание
В первом примере возможные пары \((r_0, r_1)\) выглядят следующим образом:
- «a», «aaaaa»
- «aa», «aaaa»
- «aaaa», «aa»
- «aaaaa», «a»
Пара «aaa», «aaa» не разрешена, так как \(r_0\) и \(r_1\) должны быть различными.
Во втором примере возможны следующие пары:
- «ko», «kokotlin»
- «koko», «tlin»
Примеры
| № | Входные данные | Выходные данные |
|
1
|
01
aaaaaa
|
4
|
|
2
|
001
kokokokotlin
|
2
|