Distinct Merged Melodies

You are given two strings melody1 and melody2 which represent two melodies. You need to count the number of distinct merged melodies that can be formed by interleaving the two melodies such that the relative order of characters in each melody is preserved.

This problem is equivalent to counting the number of distinct interleavings of two sequences, which can be formulated as the binomial coefficient:

$$\binom{n+m}{n}$$

where n and m are the lengths of melody1 and melody2 respectively.

For example, if melody1 = "abc" and melody2 = "def", then the answer is 20 because there are 20 ways to interleave these two strings while preserving the order within each string.

inputFormat

The input consists of two lines. The first line contains the string melody1 and the second line contains the string melody2. Note that one or both of these strings can be empty.

outputFormat

Output a single integer which is the number of distinct merged melodies that can be formed by interleaving the two input strings.## sample

abc
def

20