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 $10^9+7$. ### Constraints - $1 \le n \le 1000$. - $|S| = n$. - $|T| \le |S|$. ### Example Input: ``` 1 c b ``` Output: ``` 2 ```