Regular Expression Matching

Problem statement

A log filter uses a small pattern language to decide whether an entire message has the required form. A dot stands for any one letter, while a star lets the immediately preceding element repeat zero or more times. Your task Determine whether pattern p matches the whole string s. Ordinary letters match themselves, . matches any single character, and x* matches zero or more occurrences of element x, which may itself be a dot. Important details This is full-string matching, not substring search. A star never appears first or immediately after another star. Zero repetitions can make a pattern such as a* match an empty string. The star is not a standalone wildcard. Worked example For s = aab and p = c*a*b, use zero c letters, two a letters and one b. The entire string matches, giving true.

Input format

Two full lines: s then p. Either line may be empty.

Output format

Print true if the condition holds, otherwise false.

Constraints

0 <= lengths <= 20; s contains lowercase letters; p contains lowercase letters, . and valid * operators.

Sample input

aab
c*a*b

Sample output

true