Rock is rock too

Interview

Time limit2sMemory limit512 MB

Summary

Count the subsequences of a string of up to 1,000,000 uppercase letters that spell ROCK, modulo 1e9+7.

Level: Easy3 of 10
Topics: Dynamic programming, String
Solved: No attempts yet

Problem

나락도 락이다. 부모님께 온 연락도 락이다. 오락가락?도 락? 이다.?

Given a string $S$ of length $N$ made of uppercase English letters, count its subsequences that end with ROCK. Print the count modulo $10^9+7$ .

Input

The first line contains the length $N$ of the string $S$ . $(4 \leq N \leq 1\ 000\ 000)$

The second line contains the string $S$ , made of uppercase English letters only.

Output

Print the number of subsequences of $S$ that end with ROCK, modulo $10^9 + 7$ .

Hint

A subsequence of a string is a string obtained by deleting some characters from it. Deleting no characters is also allowed. For example, aan is a subsequence of hanyang.

Examples2

Example 1
Input
```
6
NAROCK
```
Expected output
```
4
```
Example 2
Input
```
5
RROCK
```
Expected output
```
3
```