Problem F
Word Puzzle
Young Anna recently indulges in a word puzzle app on her phone. A word puzzle is a single English word with several blanks. Each blank represents a letter to be filled. For example, the word “programming” may appear as a puzzle p_o_rammin_. When solving a puzzle, Anna first clicks on a blank and then begins 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 on the first blank and type rgg. Alternatively, she may click on the second blank and then type ggr.
One day Anna shows you a puzzle that she solved along with the sequence of letters she typed. Could you tell how many different puzzles can be the one that Anna solved? Two puzzles are different if they have blanks at different positions, e.g. if the puzzle word is programming and Anna typed rgg, there can be two possible puzzles: p_o_rammin_ and pro__ammin_. As the answer can be large, output the answer modulo $1\, 000\, 000\, 007$.
Input
The first line of input has a single string $p$ giving the puzzle word ($1 \leq |p| \leq 10^5$). The second line has a single string $s$ giving the letter sequence that Anna typed ($1 \leq |s| \leq \min (50, |p|)$). Both strings contain only lowercase English letters.
Output
Output the number of different puzzles that can be the one solved by Anna, modulo $1\, 000\, 000\, 007$. If Anna can not have typed $s$ to solve the puzzle, output zero.
| Sample Input 1 | Sample Output 1 |
|---|---|
programming rgg |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
aabbaa aba |
12 |
| Sample Input 3 | Sample Output 3 |
|---|---|
acca acac |
0 |
