Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where s and t are divided into some number of substrings such that: s = s1 + s2 + ... + sn, t = t1 + t2 + ... + tm, and their interleaving is s1 + t1 + s2 + t2 + ... (or t1 + s1 + ...).

Example 1:

Input:
aabcc
dbbca
aadbbcbcac
Output: true

Example 2:

Input:
aabcc
dbbca
aadbbbaccc
Output: false

Constraints:

• 0 ≤ s1.length, s2.length ≤ 100
• s3.length == s1.length + s2.length

Input format: Three lines: s1, s2, s3.

Output format: true or false.