---
title: BOIancy
---

The *BOIancy* of a string $s$ is the number of ways one can choose indices $i$, $j$ and $k$ such that $s_is_js_k$ is "`BOI`" and $i < j < k$. Your task is to compute the BOIancy of a given string $s$.

# Input

The first line contains an integer $n$: the length of the string $s$.

The second line contains $s$. The string consists of letters `A`–`Z`.

# Output

Print the BOIancy of the string. Since the answer may be large, print it modulo $10^9 + 7$.

# Constraints

- $3 \le n \le 10^6$

# Example

Input:
```
6
BAOBOI
```

Output:
```
3
```

_Explanation_: You can take the last three characters, the characters at indices $1$, $3$ and $6$, or the characters at indices $1$, $5$ and $6$.

# Scoring

| Subtask | Constraints | Points    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 100$ | [score=1] |
| 2       | The string contains exactly one character "`O`" | [score=2] |
| 3       | No additional constraints | [score=3] |
