---
title: BOIance
---

Virknes $s$ *BOIance* ir to veidu skaits, kā var izvēlēties indeksus $i$, $j$ un $k$ tā, ka $s_is_js_k$ ir "`BOI`" un $i < j < k$. Jūsu uzdevums ir aprēķināt dotās virknes $s$ BOIanci.

# Ievaddati

Pirmajā rindā dots naturāls skaitlis $n$: virknes $s$ garums.

Otrajā rindā dota $s$. Virkne sastāv no burtiem `A`–`Z`.

# Izvaddati

Izdrukāt virknes BOIanci. Tā kā atbilde var būt liela, izdrukāt to pēc moduļa $10^9 + 7$.

# Ierobežojumi

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

# Piemērs

Ievaddati:
```
6
BAOBOI
```

Izvaddati:
```
3
```

_Paskaidrojums_: Varat ņemt pēdējos trīs simbolus, simbolus ar indeksiem $1$, $3$ un $6$, vai simbolus ar indeksiem $1$, $5$ un $6$.

# Vērtēšana

| Apakšuzdevums | Ierobežojumi | Punkti    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 100$ | [score=1] |
| 2       | Virkne satur tieši vienu rakstzīmi "`O`" | [score=2] |
| 3       | Nav papildu ierobežojumu | [score=3] |
