Summing Grassiness over Valid Segmentations

Given two strings A and B consisting only of lowercase letters, we define a segmentation of a string of length n as a sequence of indices p₀, p₁, …, p_k+1 such that

[ 0 = p_{0} < p_{1} < p_{2} < \cdots < p_{k} < p_{k+1} = n+1. ]

For each such segmentation, we call the substrings formed by the characters in positions from p_i+1 to p_i+1-1 (which may be empty) the segmented substrings.

Now, for the two strings A and B (with lengths n and m respectively), a valid understanding consists of choosing a segmentation for A and a segmentation for B that satisfy:

• The number of segmented substrings is the same (i.e. the two segmentation sequences have the same number k of internal cut positions).
• If we denote the chosen indices for A as p and for B as q (with p₀=0, p_k+1=n+1 and q₀=0, q_k+1=m+1), then for every i=1,2,…,k we have

[ A[p_{i}] = B[q_{i}], ]

where positions in the strings are 1-indexed. (Note that the boundary indices p₀ and p_k+1 are not characters of the string.)

For a given segmentation sequence, the grassiness is defined as the sum of the squares of the lengths of every segmented substring. That is, for the segmentation for A the contribution is

[ \sum_{i=0}^{k} (p_{i+1} - p_{i} - 1)^2, ]

and similarly for B. The grassiness of a valid understanding is the sum of these two contributions.

Your task is to compute the sum of the grassiness for all valid understandings modulo \(10^9+7\>.

Note: The valid segmentation may be empty (i.e. no internal cutting points) and in that case the grassiness is n² + m², where n and m are the lengths of A and B respectively.

inputFormat

The input consists of two lines. The first line contains the string A and the second line contains the string B.

Both strings consist only of lowercase letters.

outputFormat

Output a single integer: the sum of the grassiness of all valid understandings, taken modulo \(10^9+7\).

sample

ab
ab

12