Problem E. Equipattern

Author:M. Sporyshev   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Young designer Vasya creates logo for his company. He imagines it to be a company name, each letter colored either blue or orange.

Vasya wants to color letters so that the name consisted of single-color substrings of equal length. Color of sequential substrings must alternate. In other words if first X letters are colored orange, next X must be colored blue etc.

For each letter of the alphabet, Vasya decided if it is allowed to be colored blue, orange, either of those colors, or not allowed to be used at all. Vasya wants to color company name in two colors so that his requirements for splitting into substrings and constraints on letter colors are satisfied.

Your program must calculate number of different ways Vasya may color his company name.

Input file format

First line of input file contains a string of letters which may be colored blue.

Second line of input file contains a string of letters which may be colored orange.

Third line of input file contains a string of letters — company name which must be colored.

Output file format

Output file must contain a single integer — number of different ways to color company name.

Constraints

All strings consist of small Latin letters. String length is not more than 105.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
a
b
abc
0
2
a
b
ab
1

0.089s 0.014s 13