Given an input string s and a pattern p, implement regular expression matching with support for . and * where:

• . Matches any single character.
• * Matches zero or more of the preceding element.

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

Example 1:

Input:
aa
a*
Output: true

Example 2:

Input:
aab
c*a*b
Output: true

Example 3:

Input:
mississippi
mis*is*p*.
Output: false

Constraints:

• 1 ≤ s.length ≤ 20
• 1 ≤ p.length ≤ 30

Input format: Two lines: string s, pattern p.

Output format: true or false.