---
title: BOIleiki
---

*BOIleiki* strengs $s$ skilgreindur sem fjöldi leiða til að velja þrjár vísa $i$, $j$ og $k$ þannig að $s_is_js_k$ myndar "`BOI`" og $i < j < k$. Þitt verkefni er að finna BOIleikan fyrir gefinn streng $s$.

# Intak

Fyrsta lína inniheldur eina tölu $n$: lengd strengs $s$.

Önnur lína inniheldur streng $s$. Strengurinn inniheldur aðeins stafina `A`–`Z`.

# Úttak

Prentið BOIleikan strengs. Þar sem svarið getur verið stórt, prentið svarið mátað við $10^9 + 7$.

# Takmarkanir

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

# Dæmi

Intak:
```
6
BAOBOI
```

Úttak:
```
3
```

_Útskíring_: Þú getur valið síðustu þrjá stafi, stafina á stöðum $1$, $3$ og $6$ eða stafina á stöðum $1$, $5$ og $6$.

# Stigagjöf

| Hópur | Takmarkanir | Stig |
| :-----: | ----------- | :-------: |
| 1       | $n \le 100$ | [score=1] |
| 2       | Strengurinn er nákvæmlega með einn staf "`O`" | [score=2] |
| 3       | Engar frekari takmarkanir | [score=3] |
