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 = . 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
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
The input file contains two strings Y and B consisting of only lowercase letter of english alphabet.
Print the summation of Val for all possible values of A. Answer can be very large so mod it by .
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 = .
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.