Processing math: 100%
Taboo substring - MarisaOJ: Marisa Online Judge

Taboo substring

Time limit: 1000 ms
Memory limit: 256 MB
Find the number of strings of length n that lexicographically smaller or equal to S that do not contain T as substring. ### Input - The first line contains an integer n. - The second line contains string S. - The third line contains string T. ### Output - Print the number of satisfied strings, modulo 109+7. ### Constraints - 1≤n≤1000. - |S|=n. - |T|≤|S|. ### Example Input: 1cb Output: 2