Given two non-empty strings str1 and str2, both the strings consist of only lowercase Latin letters. Your task is to calculate the number of different pairs of (a b) such that a is a substring of str1, b is a subsequence of str2, and the content of a and b are the same.
A string s is called a substring of str, if you can form s from str by removing characters from the start and end of str. Two substrings str[x1...y1] and str[x2...y2] are considered different if x1 != x2 or y1 != y2.
For example - "uber" and "eats" are two different substrings of "ubereats" whereas "ubee" is not a substring
A string s is called a subsequence of str, if you can form s from str by removing characters at any position of str. Two subsequences p and q are considered different if at least one character present in p has a different position in the original string for the corresponding character in q.
For example - "ubee" and "ubea" are two different subsequences of "ubereats" whereas "uby" is not a subsequence
SAMPLE INPUT
str1 = "aa"
str2 = "aa"
SAMPLE OUTPUT
5
EXPLANATION
Following are the valid (a b) pairs -
(str1[1..1] str2[1..1])
(str1[1..1] str2[2..2])
(str1[2..2] str2[1..1])
(str1[2..2] str2[2..2])
(str1[1..2] str2[1..2])
[execution time limit] 1 seconds (cpp)
[input] string str1
The First Input string consists of lowercase Latin letters [1 <= length(str1) <= 2000]
[input] string str2
The second input string consists of lowercase Latin letters [ 1 <= length(str2) <= 2000]
[output] integer
The number of different (a b) pairs such that "a" is a substring of str1, "b" is a subsequence of str2 and the content of "a" and "b" are the same. The answer can be large, print it modulo 1000000007 (1e9 + 7).