Задача E. Equipattern ≡

Условие

Юный дизайнер Вася разрабатывает логотип для своей компании. Он представляет его в виде имени компании, в котором каждая буква покрашена в синий или оранжевый цвет.

Вася хочет раскрасить буквы так, чтобы название состояло из одноцветных подстрок одинаковой длины. Цвета таких подстрок должны чередоваться. То есть если первые X букв покрасить в оранжевый цвет, то следующие X букв нужно красить в синий и т.д.

Для каждой буквы алфавита Вася решил, можно ли её раскрашивать в синий, оранжевый, любой из этих цветов, или вообще нельзя использовать. есть четкое представление о том, какие буквы можно красить в синий, Вася хочет покрасить строку в два цвета так, чтобы его требования к разбивке на подстроки и ограничения на цвета букв были соблюдены.

Напишите программу, определяющую, сколькими различными способами Вася может покрасить название своей компании.

Формат входного файла

Первая строка входного файла содержит символы, которые можно красить в синий цвет.

Вторая строка входного файла содержит символы, которые можно красить в оранжевый цвет.

Третья строка входного файла содержит строку, которую необходимо покрасить.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество способов покрасить строку.

Ограничения

Все строк состоят из малых латинских букв. Длина строк не превосходит 10⁵.

Примеры тестов

a
b
abc

0

a
b
ab

1