Marisa - MarisaOJ: Marisa Online Judge

Marisa

Time limit: 1000 ms
Memory limit: 256 MB
Given a string $S$, count the number of non-contiguous subsequences of $S$ that form the string `marisa`. ### Input - A single line containing the string $S$. ### Output - Output a single integer representing the number of non-contiguous subsequences of $S$ that form the string `marisa`, modulo $10^9+7$. ### Constraints - $1 \le |S| \le 10^5$ ### Example Input: ``` marisa ``` Output: ``` 1 ```