Regular Expression Matching

You are given two strings: a text string s and a pattern string p. The pattern may contain the special characters . and *, where:

• . matches any single character.
• * matches zero or more occurrences of the element immediately preceding it.

Your task is to determine if the pattern p matches the entire text s. In other words, implement the function such that it returns true if and only if the pattern matches the whole input string.

The matching should cover the entire input string (not partial).

For any regular expression concept used in this problem, refer to the formula below:

\( dp[i][j] = dp[i-1][j-1] \) if \( s_i = p_j \) or \( p_j = . \). Also, if \( p_j = * \), then \( dp[i][j] = dp[i][j-2] \) or \( dp[i][j] = dp[i-1][j] \) provided that \( s_i = p_{j-1} \) or \( p_{j-1} = . \).

inputFormat

The input is given via stdin and consists of two lines:

1. The first line contains the string s (the text).
2. The second line contains the string p (the pattern).

outputFormat

Output a single line to stdout: print true if the entire text matches the pattern; otherwise, print false.

## sample

aab
c*a*b

true