Wildcard Pattern Matching

You are given two strings: an input string S containing only lowercase alphabetical characters and a pattern P which may contain lowercase alphabetical characters along with the wildcard characters * and ?.

The wildcard character * can match zero or more characters, while ? matches exactly one character. Your task is to determine if the pattern P matches the entire string S.

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

---

Matching Rules:

• * can match any sequence of characters (including the empty sequence).
• ? matches exactly one character.
• All other characters in P must match exactly with the corresponding characters in S.

Mathematically, if we let dp[i][j] be a boolean value denoting whether the first i characters of S can be matched by the first j characters of P, then the recurrence is defined as follows:

\[ \begin{align*} dp[0][0] & = 1, \\ \text{for } j \ge 1,\quad dp[0][j] & = \begin{cases} dp[0][j-1] & \text{if } P[j-1]=='*' \\ 0 & \text{otherwise} \end{cases}, \\ \text{for } i,j \ge 1,\quad dp[i][j] & = \begin{cases} dp[i-1][j] \;\text{or}\; dp[i][j-1] & \text{if } P[j-1]=='*', \\ dp[i-1][j-1] & \text{if } P[j-1]=='?' \text{ or } S[i-1]==P[j-1], \\ 0 & \text{otherwise}. \end{cases} \end{align*} \]

Return 1 if P matches S entirely, otherwise return 0.

inputFormat

The input consists of two lines:

• The first line contains the string S.
• The second line contains the pattern P which may contain lowercase letters along with the wildcard characters * and ?.

You may assume that both S and P have lengths within reasonable limits.

outputFormat

Output a single integer (1 or 0):

• 1 if the pattern P matches the entire string S.
• 0 otherwise.

## sample

abcde
a*c?e

1