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(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.**

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

$1\leq |Y| \leq 10000$

$1 \leq |B| \leq 100$

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

Input | Output |
---|---|

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(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. |

Input | Output |
---|---|

zzzzawsad abcd | 914424997 |

Input | Output |
---|---|

ausdhasjcnaksjdaoasdasd abc | 433176291 |

Toph uses cookies. By continuing you agree to our Cookie Policy.