题目描述

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

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

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

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

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

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

输入格式

第一行一个整数 n 。

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

输出格式

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

样例输入输出

样例 1

• 样例输入 1：

4
NNOI

• 样例输出 1：

2

样例 2

• 样例输入 2：

6
NNOOII

• 样例输出 2：

8

样例 3

• 样例输入 3：

6
NOOIII

• 样例输出 3：

6

Hint

数据范围

• 对于 60% 的数据，满足 n ≤ 1000 。
• 对于 100% 的数据，满足 n ≤ 10^5 。