---
title: BOInantsus
---

Sõne $s$ *BOInantsus* on võimaluste arv valida indeksid $i$, $j$ ja $k$ nii, et $s_is_js_k$ on "`BOI`" ja $i < j < k$. Sinu ülesandeks on arvutada sõne $s$ BOInantsus.

# Sisend

Esimesel real on täisarv $n$: sõne $s$ pikkus.

Teisel real on $s$. Sõne koosneb tähtedest `A`–`Z`.

# Väljund

Väljasta sõne BOInantsus. Kuna vastus võib olla suur, väljasta see mooduli $10^9+7$ järgi. 

# Piirangud

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

# Näide

Sisend:
```
6
BAOBOI
```

Väljund:
```
3
```

_Selgitus_: Võimalikud valikud on viimased kolm indeksit, tähed indeksitel $1$, $3$ ja $6$, või tähed indeksitel $1$, $5$ ja $6$.

# Hindamine

| Grupp | Piirangud | Punktid    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 100$ | [score=1] |
| 2       | Sõnes on täpselt üks täht "`O`" | [score=2] |
| 3       | Lisapiirangud puuduvad | [score=3] |
