Count Distinct Interleavings

You are given two strings S and T. Your task is to count the number of distinct sequences U that can be formed by interleaving the characters of S and T while maintaining the relative order of characters in each string.

Formally, if S has length N and T has length M, you should find the number of distinct sequences U which is equal to the number of ways to interleave S and T. Since the result can be large, output it modulo \(10^9+7\).

Note: The interleaving must keep the order of characters in S and T intact.

inputFormat

The input consists of two lines. The first line contains the string S and the second line contains the string T. Both strings can be empty.

outputFormat

Output a single integer which is the number of distinct interleavings modulo \(10^9+7\>.

abc
def

20