---
title: BOIancy
---

*BOIancy* рядка $s$ — це кількість способів вибрати індекси $i$, $j$ та $k$ такі, що $s_is_js_k$ утворює "`BOI`" і $i < j < k$. Ваше завдання — обчислити BOIancy заданого рядка $s$.

# Вхідні дані

Перший рядок містить ціле число $n$: довжину рядка $s$.

Другий рядок містить $s$. Рядок складається з літер `A`–`Z`.

# Вихідні дані

Виведіть BOIancy рядка. Оскільки відповідь може бути великою, виведіть її за модулем $10^9 + 7$.

# Обмеження

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

# Приклад

Вхідні дані:
```
6
BAOBOI
```

Вихідні дані:
```
3
```

_Пояснення_: Можна взяти три останні символи, символи з індексами $1$, $3$ і $6$, або символи з індексами $1$, $5$ і $6$.

# Оцінювання

| Підзадача | Обмеження | Бали    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 100$ | [score=1] |
| 2       | Рядок містить рівно один символ "`O`" | [score=2] |
| 3       | Без додаткових обмежень| [score=3] |
