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
```
