Limits 2s, 64 MB

After the death of Mysterio, People started hating Peter Parker. Peter and his relatives were arrested for interrogation. During that interrogation, Ned Leeds told the officer that once he helped spider man by hacking his suit.

Happy Hogan appoints Matt Murdock as Peter Parker's lawyer. After the interrogation finished, Matt came to peter parker's house and told Ned Leeds, “You were being so dumb during interrogation. Why would you tell them about Peter? This is not really funny what you did! So, what I’m gonna do is, I’ll lock your mouth up like Bane from DC Universe(yes! that’s a crossover there!) as a punishment. And the only way you can unlock/disarm it is by solving the following problem just because I care for you in some way.”

Suppose, there are two strings, A and B. A and B consist of only lowercase letters of English alphabets. You have to do the following-

Step - 1: Take a prefix from A and name it S.

Step - 2: Check if B is a suffix of S.

Step - 3: Calculate a value X. If B is not a suffix of S, X=0. Else, X = f(L3)f(L^3). Where L is the length of S. [The definition of f(n) is given below]

Finally, Calculate a value Val which is the summation of all the values got from Step 3 for all the prefixes of A.

Now, Ned says, Ow! It's an easy task.

Matt replied I am not finished yet, you idiot!

I will provide you with two strings Y and B. Basically the value of A is any lexicographically smaller or equal string compared to Y with the same string length. You have to calculate the summation of Val for all possible values of A.

Input

The input file contains two strings Y and B consisting of only lowercase letter of english alphabet.

1Y100001\leq |Y| \leq 10000

1B1001 \leq |B| \leq 100

Output

Print the summation of Val for all possible values of A. Answer can be very large so mod it by 109+7(1000000007)10^9 + 7 (1000000007).

Samples

InputOutput
af
a
3815

All the strings of the same length of “ab” and lexicographically less than equal to “af” are: aa,ab,ac,ad,ae,af.

For, A = “aa”, has 2 prefixes. Those are “a” and “aa”, both of them contain the string B as a suffix. So, Val = f(13)+f(23)=3695f(1^3) + f(2^3) = 3695.

Same as for all other strings,

For, A = ab, Val = 24.

For, A = ac, Val = 24.

For, A = ad, Val = 24.

For, A = ae, Val = 24.

For, A = af, Val = 24.

Total value 3815.

InputOutput
zzzzawsad
abcd
914424997
InputOutput
ausdhasjcnaksjdaoasdasd
abc
433176291

Submit

Login to submit.

Statistics

13% Solution Ratio
steinumEarliest, Nov '22
user.1267Fastest, 0.1s
steinumLightest, 5.9 MB
user.1267Shortest, 5837B
Toph uses cookies. By continuing you agree to our Cookie Policy.