题目描述

小胡上课开小差了被老师发现了。

他在笔记本上写了一长串字母，字母仅包含 N、O 和 I 这三种。

老师为了惩罚他，让他算出 N、O、I 这三个字母按顺序构成 NOI 这个词的次数。

老师要求，构成的 NOI 仅在乎每个字符是否按找顺序出现，不在乎单词之间有重叠的字符。

例如，NOI 在 NIOI 中出现一次，在 NNOI 中出现两次，在 NNOOII 中出现八次。

小胡已经算糊涂了，后悔没有好好听讲，请你帮他算一算。

输入格式

第一行一个整数 $n$。

第二行有 $n$ 个字符，每个字符是 N、O、I 中的一个。

输出格式

输出按照题意，NOI 在序列中出现的次数。

样例

4
NNOI

2

6
NNOOII

8

6
NOOIII

6

数据范围

• 对于 $60\%$ 的数据，满足 $n \le 1000$
• 对于 $100\%$ 的数据，满足 $n \le 10^5$