Word Puzzle
Time limit11sMemory limit1024 MB
Count the blank placements in a word such that typing the given key sequence in circular order fills them all correctly, modulo 1e9+7.
- Level
Medium7 of 10
- Topics
- Combinatorics, String, Dynamic programming, Math
- Solved
- No attempts yet
Problem
Young Anna has recently been absorbed in a word puzzle app on her phone. A word puzzle is a single English word with several blanks. Each blank represents one letter to fill in. For example, the word "programming" may appear as the puzzle p_o_rammin_. When solving a puzzle, Anna first clicks a blank and then starts typing letters. The app automatically advances to the next blank once Anna types a letter. When there are no more blanks to the right of the filled letter, the app jumps back to the beginning of the word and advances from there. Anna keeps typing until all blanks are filled. To solve the puzzle p_o_rammin_, Anna may click the first blank and type rgg. Alternatively, she may click the second blank and type ggr.
One day Anna shows you a puzzle she solved along with the sequence of letters she typed. How many different puzzles could be the one Anna solved? Two puzzles are different if their blanks are at different positions. For example, if the puzzle word is programming and Anna typed rgg, there are two possible puzzles: p_o_rammin_ and pro__ammin_. Since the answer can be large, output it modulo 1,000,000,007.
Input
The first line contains a single string p giving the puzzle word. (1 ≤ |p| ≤ 105) The second line contains a single string s giving the sequence of letters Anna typed. (1 ≤ |s| ≤ min(50, |p|)) Both strings consist only of lowercase English letters.
Output
Output the number of different puzzles that could be the one Anna solved, modulo 1,000,000,007. If Anna could not have typed s to solve the puzzle, output zero.