E. Проверь транскрипцию
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Один из друзей Аркадия работает на огромном радиотелескопе. Несколько десятилетий назад телескоп послал сигнал $$$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$$$.

Входные данные

Первая строка содержит строку $$$s$$$ ($$$2 \le |s| \le 10^5$$$), задающую исходный сигнал и состоящую только из нулей и единиц.

Вторая строка содержит строку $$$t$$$ ($$$1 \le |t| \le 10^6$$$), состоящую только из строчных латинских букв и задающую полученный сигнал.

Гарантируется, что строка $$$s$$$ содержит хотя бы один «0» и хотя бы одну «1».

Выходные данные

Выведите одно целое число — количество пар строк $$$r_0$$$ и $$$r_1$$$, которые переводят $$$s$$$ в $$$t$$$.

В случае, если ни одной подходящей пары нет, выведите $$$0$$$.

Примеры
Входные данные
01
aaaaaa
Выходные данные
4
Входные данные
001
kokokokotlin
Выходные данные
2
Примечание

В первом примере возможные пары $$$(r_0, r_1)$$$ выглядят следующим образом:

  • «a», «aaaaa»
  • «aa», «aaaa»
  • «aaaa», «aa»
  • «aaaaa», «a»

Пара «aaa», «aaa» не разрешена, так как $$$r_0$$$ и $$$r_1$$$ должны быть различными.

Во втором примере возможны следующие пары:

  • «ko», «kokotlin»
  • «koko», «tlin»