---
title: BOImaisuus
---

Merkkijonon $s$ *BOImaisuus* tarkoittaa, monellako tavalla voidaan valita kohdat $i$, $j$ ja $k$ niin, että $s_is_js_k$ on "`BOI`" ja $i < j < k$. Tehtäväsi on laskea annetun merkkijonon $s$ BOImaisuus.

# Syöte

Ensimmäisellä rivillä on kokonaisluku $n$: merkkijonon $s$ pituus.

Toisella rivillä on merkkijono $s$. Merkkijono muodostuu kirjaimista `A`–`Z`.

# Tuloste

Tulosta merkkijonon BOImaisuus. Koska vastaus voi olla suuri, tulosta se modulo $10^9 + 7$.

# Rajat

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

# Esimerkki

Syöte:
```
6
BAOBOI
```

Tuloste:
```
3
```

_Selitys_: Voit valita kolme viimeistä merkkiä, kohdissa $1$, $3$ ja $6$ olevat merkit tai kohdissa $1$, $5$ ja $6$ olevat merkit.

# Pisteytys

| Osatehtävä | Rajoitukset | Pisteet    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 100$ | [score=1] |
| 2       | Merkkijonossa on tasan yksi merkki "`O`" | [score=2] |
| 3       | Ei lisärajoituksia | [score=3] |
