---
title: BOIškumas
---

Raidžių sekos $s$ *BOIškumas* yra lygus skaičiui būdų parinkti pozicijas $i$, $j$ ir $k$ taip, kad $s_is_js_k$ yra "`BOI`" bei $i < j < k$. Apskaičiuokite duotos raidžių sekos $s$ BOIškumą.

# Pradiniai duomenys

Pirmoje eilutėje pateiktas sveikasis skaičius $n$ – raidžių sekos $s$ ilgis.

Antroje eilutėje pateikta seka $s$. Seką sudaro raidės `A`–`Z`.

# Išvestis

Išveskite raidžių sekos BOIškumą moduliu $10^9 + 7$.

# Ribojimai

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

# Pavyzdys

Pradiniai duomenys:
```
6
BAOBOI
```

Išvestis:
```
3
```

_Paaiškinimas_: galite parinkti tris paskutines raides arba raides su pozicijomis $1$, $3$ ir $6$, arba raides su pozicijomis $1$, $5$ ir $6$.

# Vertinimas

| Dalinė užduotis | Ribojimai | Taškai    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 100$ | [score=1] |
| 2       | Sekoje yra lygiai viena raidė "`O`" | [score=2] |
| 3       | Papildomų ribojimų nėra | [score=3] |
